On the 20th of October, we will replace hardware of the main server of Jutge.org. It is therefore expected that the system will be down from 00:00 to 08:00 (CEST) that day.

Given a DAG G with n vertices and m arcs with *unique* positive
integer labels on the arcs,
find the smallest lexicographic path
(considering the labels on the arcs, not the numbers of the vertices)
between 0 and n−1.

A DAG (directed acyclic graph) is a directed graph without cycles. Given two
sequences of integers a_{1}, …, a_{k} and b_{1}, …, b_{l}, we say a is
lexicographically smaller than b when, for the first i such that a_{i} ≠
b_{i}, we have that a_{i} < b_{i}, or when k < l in case that no such i exists.

Input

Input consists of several cases. Every case consists of n and m,
followed by m triples u, v, w
meaning that there is an arc from u to v with label w.
Assume 2 ≤ n ≤ 10^{5},
0 ≤ m ≤ 5n,
1 ≤ w ≤ 10^{9},
that vertices are numbered between 0 and n−1,
u ≠ v,
and that there is no more than one arc from u to v.
All w are distinct in every given case.

Output

For every case, print the smallest lexicographic path between 0 and n−1. Print the labels separated by spaces. If there is no path between 0 and n−1, print -1.

Public test cases

**Input**

3 3 0 1 100 1 2 300 0 2 200 4 5 2 3 50 1 2 20 0 1 10 1 3 30 0 2 40 2 1 1 0 1000000000

**Output**

100 300 10 20 50 -1

Information

- Author
- Miquel Ortega
- Language
- English
- Official solutions
- C++
- User solutions
- C++