Write a program that, given a directed multigraph with arcs with positive costs, computes the cost of the second cheapest walk from vertex 0 to every other vertex. Remember that a multigraph may have arcs from x to x, and more than one arc from x to y. Also remember that a walk can repeat vertices and arcs.

Input

Input consists of several cases.
Every case begins with the number of vertices n and the number of arcs m,
followed by m triples x y c
to indicate an arc from x to y with cost c.
Assume 2 ≤ n ≤ 10^{4},
0 ≤ m ≤ 5n,
that vertices are numbered from 0 to n − 1,
and that every cost c is an integer number between 1 and 10^{4}.

Output

For every case, print the second minimum cost of walking from 0 to the rest of vertices, ordered from 1 to n − 1. If there is no second best walk to some vertex, just print “no”. Print a line with ten dashes at the end of every case.

Public test cases

**Input**

4 3 0 1 100 0 3 200 1 3 50 5 8 0 4 42 0 4 12 1 0 10000 0 1 7 0 3 100 3 3 5000 3 2 23 0 2 6000

**Output**

no no 200 ---------- 10014 5123 5100 42 ----------

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++