Submit | All submissions | Best solutions | Back to list |
PCYCLE - Exploring the maze |
English | Vietnamese |
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 |