2109 - テレポート移動網２０２３

問題

イヅア国には$N$個の街と$N-1$本の道路がある。$i$番目の道路は街$A_i$と街$B_i$を双方向に結んでおり、その通行コストは$C_i$である。また、どの街からも、いくつかの道路を通って他のすべての街へたどり着くことができる。

イヅア国には、国民の移動をより便利にするために、街1に管制施設が、それ以外の街にはテレポート装置が設置されている。街$i$に設置されたテレポート装置を使って、以下の条件を満たす街$k$へコスト$T_i$で移動することができる。

• 街$i$と街$k$との距離が$D_i$以下である
• 街1と街$i$との距離と、街1と街$k$との距離が等しい

ここで、街$u$と街$v$との距離を、$u$から$v$へ道路のみを用いて移動するときに使う必要のある最小の道路の数とします。

イヅア国の街の数、道路とそれらのコスト、テレポート装置の情報、始点の街の番号$S$,終点の街の番号$G$が与えられる。街$S$から街$G$へ道路とテレポート装置を使ってたどり着くのにかかるコストの合計の最小値を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $S$ $G$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
:
$A_{N-1}$ $B_{N-1}$ $C_{N-1}$
$T_2$ $D_2$
$T_3$ $D_3$
:
$T_N$ $D_N$

1行目に街の数$N$ ($2 \leq N \leq 100,000$)、始点の街の番号$S$ ($1 \leq S \leq N$)、終点の街の番号$G$ ($1 \leq G \leq N$)が与えられる。続く$N-1$行に、$i$番目の道路の両端の街$A_i,B_i$ ($1 \leq A_i < B_i\leq N$)およびその通行コスト$C_i$ ($1 \leq C_i \leq 1,000,000,000$)が、すべて整数で与えられる。続く$N-1$行に、街$i$に設置されているテレポート装置を使用するコスト$T_i$ ($1 \leq T_i \leq 1,000,000,000$)と、移動できる距離の制約$D_i$ ($1 \leq D_i \leq 200,000$)が、すべて整数で与えられる。

出力

コストの合計の最小値を1行に出力する。

入出力例

入力例１

6 3 6
1 2 4
2 3 1
2 4 5
1 5 2
5 6 3
2 3
6 3
5 2
5 1
8 6

出力例１

6

入力例２

6 3 6
1 2 4
2 3 1
2 4 1
1 5 2
5 6 3
2 8
6 8
1 8
5 8
8 8

出力例２

3