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