Giải bài trực tuyến

In a maze, there are N rooms and some corridors connecting the rooms. There is at most one corridor connecting each pair of rooms.

An explorer wants to explore that maze. He'll start at a room and go along all the corridors so that each corridor is passed exactly once. Then he'll return to the starting point. Each corridor is assigned a value c meaning that when going along that corridor, the explorer's energy points will be add up with c unit(s) (c may be negative). The explorer starts with 0 energy point. He'll die if after passing a corridor, his energy point is negative.

Your task is to help the explorer find a safe journey satisfying the given conditions.

Input

• The first line contains two integers N and M (1 ≤ N ≤ 200).
• The i^th line in the next M lines contains three integers u, v, c representing a corridor connecting room u and room v with c energy points. (|c| ≤ 10000).

Output

• If there is no safe journey, print -1. Otherwise, print M+1 integers which are indexes of the rooms along the journey.

Example

Input
3 3
1 2 2
1 3 -1
2 3 -1

Output
2 1 3 2