Submit solution
Points:
0.31 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
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