VM 08 Bài 20 - Mê cung

View as PDF

Submit solution


Points: 0.31 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon '08 - Round 4Problem Setter: Nguyễn Minh Hiếu
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho đồ thị ~N~ đỉnh, ~M~ cạnh. Giữa 2 đỉnh có tối đa 1 cạnh. Mỗi cạnh có trọng số.

Tìm 1 chu trình đi qua tất cả các cạnh của đồ thị, sao cho tại mỗi thời điểm, tổng trọng số các cạnh đi qua không âm.

Input

  • Dòng 1: ~N~ và ~M~. ~(1 \le N \le 200)~.
  • M dòng tiếp, mỗi dòng gồm 3 số ~u~, ~v~, ~c~ thể hiện 1 cạnh 2 chiều nối ~u~ và ~v~ với trọng số ~c~. Trọng số các cạnh có trị tuyệt đối không quá 10,000.

Output

Nếu vô nghiệm, in ra ~-1~. Ngược lại, in ra ~M+1~ số thể hiện các đỉnh đi qua trên đường đi.

Sample Input

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

Sample Output

2 1 3 2

Comments

Please read the guidelines before commenting.


There are no comments at the moment.