当前没有测试数据。

IOI 町には $N$ 個の交差点があり，$1$ から $N$ までの番号が付いている．また，$M$ 本の道があり，$1$ から $M$ までの番号が付いている．それぞれの道は $2$ 個の異なる交差点を双方向に結んでいる．道 $i$ ($1 \\leqq i \\leqq M$) は交差点 $A_i$ と交差点 $B_i$ を結んでいる．$2$ 本の異なる道が同じ交差点の組を結ぶことはない．これらの道には $1$ 以上 $M$ 以下の整数で表される色が塗られており，道 $i$ の現在の色は $C_i$ である．複数の道が同じ色で塗られているかもしれない．

JOI 社は IOI 町の交差点を移動するロボットを開発した．あなたがこのロボットに道の色を指示すると，ロボットは指示された色の道を通り隣接した交差点に移動する．ただし，ロボットが現在いる交差点につながれた道のうちに，指示された色の道が $2$ 本以上存在すると，次に進むべき道を判別できずに停止してしまう．

あなたの目的は，現在交差点 $1$ にいるロボットに何回かの指示を出して，交差点 $N$ に移動させることである．ただし，現在の道の色ではそれができるとは限らないため，何本かの道の色を事前に塗り替えることで， ロボットを交差点 $N$ に移動させることができるようにしたい．道 $i$ ($1 \\leqq i \\leqq M$) は $P_i$ 円をかけて，$1$ 以上 $M$ 以下の好きな整数の色に塗り替えることが出来る．

交差点と道の情報が与えられたとき，必要な金額の最小値を求めるプログラムを作成せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 $N$ に移動させることができない場合は，代わりに -1 を出力せよ．

---

入力

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

$N$ $M$ $A_1$ $B_1$ $C_1$ $P_1$ $\\vdots$ $A_M$ $B_M$ $C_M$ $P_M$

出力

標準出力に必要な金額の最小値を $1$ 行で出力せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 $N$ に移動させることができない場合は，代わりに -1 を出力せよ．

---

制約

• $2 \\leqq N \\leqq 100\\,000$．
• $1 \\leqq M \\leqq 200\\,000$．
• $1 \\leqq A_i < B_i \\leqq N$ ($1 \\leqq i \\leqq M$)．
• $(A_i, B_i) \\neq (A_j, B_j)$ ($1 \\leqq i < j \\leqq M$)．
• $1 \\leqq C_i \\leqq M$ ($1 \\leqq i \\leqq M$)．
• $1 \\leqq P_i \\leqq 1\\,000\\,000\\,000$ ($1 \\leqq i \\leqq M$)．

小課題

1. ($34$ 点) $N \\leqq 1\\,000$，$M \\leqq 2\\,000$．
2. ($24$ 点) $P_i = 1$ ($1 \\leqq i \\leqq M$)．
3. ($42$ 点) 追加の制約はない．

---

入力例 1

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

出力例 1

3

$1$ 円で道 $4$ を色 $3$ から色 $4$ に塗り替え，$2$ 円で道 $6$ を色 $4$ から色 $2$ に塗り替える．合計 $3$ 円かかる．

この結果，交差点 $1$ にいるロボットに色 $2$ を指示することで，ロボットを交差点 $2$ に移動させることができる．続けて，ロボットに色 $4$ を指示することで，ロボットを交差点 $4$ に移動させることができる．

$2$ 円以下でロボットを交差点 $4$ に移動させることは不可能であるため，$3$ を出力する．

---

入力例 2

5 2
1 4 1 2
3 5 1 4

出力例 2

-1

道をどのように塗り替えても，ロボットを交差点 $5$ に移動させることはできない．したがって，$\-1$ を出力する．

---

入力例 3

5 7
2 3 7 1
1 4 5 1
4 5 3 1
3 4 7 1
2 4 3 1
3 5 6 1
1 2 5 1

出力例 3

1

この入力例は小課題 $2$ の制約を満たす．

---

入力例 4

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

出力例 4

7