問題文

プリンセスの高橋さんは、森の中で迷子になってしまいました。

森には N 個の広場と M 本の道があります。広場には 1 から N までの番号が付いています。道 i は広場 a_i と広場 b_i を双方向に結んでおり、幅は c_i、長さは d_i です。複数の道が同じ広場の組を結ぶこともあります。また、どの広場からどの広場へもいくつかの道を通って到達することができます。

森には K 匹の動物がいます。動物 j は、はじめ広場 v_j にいて、大きさは x_j です。大きさが x の動物は、幅が x 以上の道だけを通ることができます。

高橋さんは、はじめ広場 1 にいて、動物には乗っていません。高橋さんは次の行動を好きな回数行えます。

• 動物に乗っていないとき、道を 1 本選んで歩いて移動する。このとき、歩行距離はその道の長さだけ増える。
• 動物に乗っていないとき、同じ広場にいる動物に乗る。
• 動物に乗っているとき、その動物が通れる道を 1 本選び、動物とともに移動する。このとき、歩行距離は増えない。
• 動物に乗っているとき、その動物から降りる。動物はその広場に残る。

高橋さんは道の幅によらず、どの道でも歩くことができます。また、道の途中で止まったり、動物に乗り降りしたりすることはできません。動物は、高橋さんが乗って移動するとき以外には移動しません。

広場 N に到達するまでの歩行距離の最小値を求めてください。

制約

• 2 \le N \le 10^5
• N-1 \le M \le 10^5
• 1 \le K \le 10^5
• 1 \le a_i \lt b_i\le N
• 1 \le c_i,d_i\le 10^9
• 1 \le v_j \le N
• 1 \le x_j \le 10^9
• 与えられるグラフは連結である
• 入力はすべて整数である

入力例 1

4 3 1
1 2 1 3
2 3 5 10
3 4 5 10
2 5

出力例 1

3

以下のようにすれば、歩行距離が 3 となります。

• 広場 1 から道 1 を用いて広場 2 まで歩く。歩行距離は 3 となる。
• 広場 2 で動物 1 に乗る。
• 動物に乗ったまま、広場 2 から道 2 を用いて広場 3 に行く。
• 動物に乗ったまま、広場 3 から道 3 を用いて広場 4 に行く。

入力例 2

3 2 1
1 2 10 4
2 3 2 7
1 5

出力例 2

7

以下のようにすれば、歩行距離が 7 となります。

• 広場 1 で動物 1 に乗る。
• 動物に乗ったまま、広場 1 から道 1 を用いて広場 2 に行く。
• 広場 2 で動物から降りる。動物 1 は広場 2 に残る。
• 広場 2 から道 2 を用いて広場 3 まで歩く。歩行距離は 7 となる。

道 2 は幅 2 ですから、大きさが 5 の動物 1 は通ることができないことに注意してください。

入力例 3

15 14 3
1 2 9 8
2 3 9 8
3 4 9 8
4 5 9 8
5 6 5 8
6 7 5 8
7 8 5 8
8 9 5 8
9 10 5 8
10 11 2 8
11 12 2 8
12 13 2 8
13 14 2 8
14 15 2 8
1 9
5 5
10 2

出力例 3

0

入力例 4

10 19 5
1 2 594909233 622379185
2 3 725115453 486137434
3 4 227907877 347378973
4 5 35626222 730377835
3 6 819140532 653954484
1 7 790169806 729923705
4 8 127763929 356749837
8 9 62511885 377315779
6 10 537489942 409936741
1 7 628157873 35857198
1 10 936797035 549456204
5 10 640646299 921436478
4 9 410095318 333337850
5 10 42622736 890036373
2 10 904887490 856341412
6 7 413238445 652816775
9 10 437102059 490707900
2 10 500383136 189664736
1 4 714288343 489127699
8 62511886
10 437102060
8 127763929
10 936797035
6 413238445

出力例 4

549456204