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₁, …, a_k and b₁, …, 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⁵, 0 ≤ m ≤ 5n, 1 ≤ w ≤ 10⁹, 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.