Smallest lexicographic path P76480


Statement
 

pdf   zip

thehtml

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 a1, …, ak and b1, …, bl, we say a is lexicographically smaller than b when, for the first i such that aibi, we have that ai < bi, 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 ≤ 105, 0 ≤ m ≤ 5n, 1 ≤ w ≤ 109, that vertices are numbered between 0 and n−1, uv, 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++