問題文

パ研王国には N 個の町 1, 2, \ldots, N と、異なる 2 つの町を双方向に繋ぐ M 個の道路 1, 2, \ldots, M があります。道路 i (1 \leq i \leq M) は町 A_i と町 B_i を双方向に繋いでおり、 2 つの異なる道路が同じ町の組を結ぶことはありません。どの町からどの町へも 0 本以上の道路を通り移動できますが、道路以外を通って町から町へ移動することはできません。

さて、今年もパ研合宿の季節がやってきました。パ研合宿は町 1 で開催されるため、全ての町から参加者が町 1 に移動します。荷物を持って移動するのは大変なので、参加者はタクシーを使って町を移動することになりました。

パ研王国には N 個のタクシー会社 1, 2, \ldots, N があり、それぞれの会社には以下のような規則があります。

• タクシー会社 i のタクシーには、町 i からのみ乗車できる。
• タクシー会社 i のタクシーの運賃は、移動した距離によらず C_i である。
• タクシー会社 i のタクシーは、乗車してから最大 R_i 本の道路しか通ることができない。

複数のタクシーを乗り継ぐこともできますが、タクシー以外の手段で町を移動してはいけません。

参加者のために、それぞれの町からタクシーのみを用いて町 1 に移動するために必要な運賃の合計の最小値を求めてください。なお、この制約下で全ての町からタクシーのみを用いて町 1 に移動できることが証明できます。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq M \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N (1 \leq i \leq M)
• (A_i, B_i) \neq (A_j, B_j) (1 \leq i < j \leq M)
• どの町からどの町へも 0 本以上の道路を通り移動できる
• 1 \leq C_i \leq 10^9 (1 \leq i \leq N)
• 1 \leq R_i \leq 10 (1 \leq i \leq N)
• 入力は全て整数

入力例 1

5 5
1 2
2 3
3 4
4 5
2 5
100 300 500 200 100
1 2 1 3 1

出力例 1

0
300
700
200
300

パ研王国は以下のようになります。

例えば、町 5 から町 1 へは以下のように移動できます。

1. 町 5 でタクシー会社 5 のタクシーに乗り、町 4 まで移動する。
2. 町 4 でタクシー会社 4 のタクシーに乗り、町 1 まで移動する。

このときに必要な運賃の合計は 100+200=300 です。運賃の合計が 300 未満となる移動方法はないため、 300 を出力します。