Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

PCYCLE - Exploring the maze

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 ith 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

Added by:Nguyen Minh Hieu
Date:2008-07-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 SCM qobi VB.NET
Resource:VNOI Marathon '08 - Round 4
Problem Setter: Nguyễn Minh Hiếu

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.