문제

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

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

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

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

입력

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

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

출력

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

제한

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

서브태스크

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

예제 설명 1

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

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

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

예제 설명 2

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

예제 설명 3

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