School Road

In the town of Aizu, where PCK lives, there are $N$ points and $M$ roads connecting each point. Each point is numbered from $1$ to $N$, and all roads can be traveled in both directions. You can also reach other points from any point by taking some of the paths.

PCK's house is at point 1 and his school is at point $N$. PCK wants to find out the shortest way to school for each of the paths he must take from all the paths in the town of Aizu. However, the route to school must meet the following conditions:

• The point included in the route to school will be passed exactly once.
• The distance is the shortest among the school routes that meet the above conditions.

You are given a number of points and information about the roads that connect the points directly. Create a program to find the distance of the school route when each path is chosen.

Input

The input is given in the following format.

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

The first line gives the number of points $N$ ($2 \leq N \leq 20$) and the number of roads $M$ ($1 \leq M \leq N(N-1)/2$). In the following $M$ lines, the information on the roads that directly connect the two points is given. $s_i$ and $t_i$ ($1 \leq s_i < t_i \leq N$) are the numbers of the two points connected by the $i$th path, and $d_i$ ($1 \leq d_i \leq 1000$) is the distance of the path. However, for any two points, no more than one road can connect them directly.

Output

The output is the $M$ lines. Output the distance of the school route when the route given in the $i$th input is always used, in the $i$th line. However, if there is no school route that uses the $i$th given road, output "-1".

Sample Input and Output

Sample Input

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

Sample Output

12
-1
9
12
9

---