AT_codequeen2026_h 迷子の森

プリンセスの高橋さんは、森の中で迷子になってしまいました。 森には $ 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 $ に到達するまでの歩行距離の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ c_1 $ $ d_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ d_2 $ $ \vdots $ $ a_M $ $ b_M $ $ c_M $ $ d_M $ $ v_1 $ $ x_1 $ $ v_2 $ $ x_2 $ $ \vdots $ $ v_K $ $ x_K $

答えを出力せよ。

### Sample Explanation 1 以下のようにすれば、歩行距離が $ 3 $ となります。 - 広場 $ 1 $ から道 $ 1 $ を用いて広場 $ 2 $ まで歩く。歩行距離は $ 3 $ となる。 - 広場 $ 2 $ で動物 $ 1 $ に乗る。 - 動物に乗ったまま、広場 $ 2 $ から道 $ 2 $ を用いて広場 $ 3 $ に行く。 - 動物に乗ったまま、広場 $ 3 $ から道 $ 3 $ を用いて広場 $ 4 $ に行く。 ### Sample Explanation 2 以下のようにすれば、歩行距離が $ 7 $ となります。 - 広場 $ 1 $ で動物 $ 1 $ に乗る。 - 動物に乗ったまま、広場 $ 1 $ から道 $ 1 $ を用いて広場 $ 2 $ に行く。 - 広場 $ 2 $ で動物から降りる。動物 $ 1 $ は広場 $ 2 $ に残る。 - 広場 $ 2 $ から道 $ 2 $ を用いて広場 $ 3 $ まで歩く。歩行距離は $ 7 $ となる。 道 $ 2 $ は幅 $ 2 $ ですから、大きさが $ 5 $ の動物 $ 1 $ は通ることができないことに注意してください。 ### Constraints - $ 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 $ - 与えられるグラフは連結である - 入力はすべて整数である