Alleyways

Minseung wants to travel from home to a destination. Between them are several intersections connected by complicated one-way alleyways.

Each alleyway has an integer value w. If w is positive, he gains that much money when using the alleyway; if w is negative, he loses that much money. If he uses the same alleyway more than once, the value is applied every time. His total amount of money may become negative.

Among all routes that start at intersection 1 and arrive at intersection n, output a route whose total value is as large as possible. If the value can be made arbitrarily large, so no optimal route exists, output -1.

The first line contains the number of intersections n (2 <= n <= 100) and the number of alleyways m (1 <= m <= 20,000).

Each of the next m lines contains three integers u, v, and w. This means there is a one-way alleyway from intersection u to intersection v. The value w (0 <= |w| <= 1,000) is the amount gained or lost when using that alleyway. A negative value means a loss, and a positive value means a gain.

Intersection numbers are integers from 1 through n. The start is intersection 1, and the destination is intersection n.

If an optimal route exists, print the intersection numbers visited from intersection 1 to intersection n, in order, separated by spaces.

If no optimal route exists, print -1. If there are multiple optimal routes, any one of them may be printed.