通学路

PCK君が住むアイヅ町には、$N$個の地点と各地点をつなぐ$M$本の道があります。地点にはそれぞれ$1$から$N$までの番号がついていて、どの道も双方向に移動することができます。また、どの地点からでも、いくつかの道を通っていけば他の地点に到達できます。

PCK君の家は地点１に、学校は地点$N$にあります。PCK君は、アイヅ町にあるすべての道から、必ず通る道を一つ選んだ場合各々について、学校に行くための最短路を調べたいと考えています。ただし、通学路は以下の条件を満たす必要があります。

• 通学路に含まれる地点はちょうど１回通る。
• 上の条件を満たす通学路の中で距離が最短である。

地点の数と、地点同士を直接つなぐ道の情報が与えられる。各道を選んだときの通学路の距離を求めるプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$ $M$
$s_1$ $t_1$ $d_1$
$s_2$ $t_2$ $d_2$
:
$s_M$ $t_M$ $d_M$

１行目に地点の数$N$ ($2 \leq N \leq 20$)と道の数$M$ ($1 \leq M \leq N(N-1)/2$)が与えられる。続く$M$行に、２つの地点を直接つなぐ道の情報が与えられる。$s_i$と$t_i$ ($1 \leq s_i < t_i \leq N$)は$i$番目の道がつなぐ２つの地点の番号であり、$d_i$ ($1 \leq d_i \leq 1000$)はその道の距離を表す。ただし、どの２つの地点についても、それらを直接つなぐ道は１本以下とする。

出力

出力は$M$行であり、入力で$i$番目に与えられた道を必ず使う場合の通学路の距離を、$i$行目に出力する。ただし、$i$番目に与えられた道を使う通学路が存在しない場合は「-1」を出力する。

入出力例

入力例

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

出力例

12
-1
9
12
9

Note

Algorithm

 

---