010 - 通学路

問題

PCK君が住むアイヅ町には、$N$個の地点と各地点をつなぐ$M$本の道があります。地点にはそれぞれ$1$から$N$までの番号がついていて、どの道も双方向に移動することができます。また、どの地点からでも、いくつかの道を通っていけば他の地点に到達できます。
PCK君の家は地点１に、学校は地点$N$にあります。PCK君は、アイヅ町にあるすべての道から、必ず通る道を一つ選んだ場合各々について、学校に行くための最短路を調べたいと考えています。ただし、通学路は以下の条件を満たす必要があります。

通学路に含まれる地点はちょうど１回通る。

上の条件を満たす通学路の中で距離が最短である。

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

入力

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

$N$ $M$
$s_1$ $t_1$ $d_1$
$s_2$ $t_2$ $d_2$
$\vdots$
$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 \leq 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