Smallest lexicographic path P76480

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, \dots, a_k$ and $b_1, \dots, b_l$, we say $a$ is lexicographically smaller than $b$ when, for the first $i$ such that $a_i \ne 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 \le n \le 10^5$, $0 \le m \le 5n$, $1 \le w \le 10^9$, that vertices are numbered between 0 and $n-1$, $u \ne 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.