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

Thám hiểm mê cung

Một mê cung gồm có N phòng và M hành lang nối các phòng, giữa hai phòng bất kì có không quá một hành lang nối chúng.
Một người muốn khám phá mê cung, anh ta sẽ xuất phát từ một phòng và đi dọc theo tất cả các hành lang sao cho mỗi hành lang được đi qua đúng một lần, rồi lại trở về vị trí xuất phát. Mỗi hành lang có một giá trị c cho biết khi đi qua nó thì năng lượng nhà thám hiểm sẽ cộng thêm với c (c có thể âm hay dương). Nhà thám hiểm bắt đầu xuất phát với năng lượng bằng 0, anh ta sẽ chết nếu sau khi đi hết một hành lang nào đó mà mức năng lượng nhỏ hơn 0.
Yêu cầu: Hãy giúp nhà thám hiểm tìm ra một hành trình an toàn thỏa mãn các yêu cầu đã đưa ra.

Dữ liệu

  • Dòng 1 là 2 số nguyên N, M. ( 1 ≤ N ≤ 200 )
  • M dòng tiếp theo, dòng thứ i gồm 3 số nguyên u, v, c cho biết có 1 hành lang nối phòng u với phòng v và giá trị năng lượng là c. ( |c| ≤ 10000 ) .

Kết quả

  • Nếu có không có hành trình nào an toàn thì ghi ra -1. Ngược lại ghi ra M+1 số nguyên là chỉ số phòng trên đường đi. Từ phòng xuất phát, qua các phòng, hành lang rồi quay trở về phòng xuất phát.

Ví dụ

Dữ liệu
3 3
1 2 2
1 3 -1
2 3 -1

Kết qủa
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.