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

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2008-07-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Nguồn bài:VNOI Marathon '08 - Round 4
Problem Setter: Nguyễn Minh Hiếu

hide comments
2015-09-22 10:36:46
last comment :v
2014-10-23 09:53:51 [CHV] Bác Thợ Sãn
first comment :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.