우체부

작은 마을에 N개의 집과 M개의 길이 있다. 각 길은 두 집을 연결하며, 길마다 우편물을 넣는 우체통이 하나 있다.

우체부는 모든 길을 정확히 한 번씩 지나면서 우편물을 수거하려고 한다. 이 마을에서는 그런 경로가 항상 존재한다.

i번째 길의 우체통에는 가중치 w[i]가 있다. 이 길을 경로에서 k번째로 지나면, k가 w[i]보다 작을 때 w[i]-k만큼 이익을 얻고, k가 w[i]보다 클 때 k-w[i]만큼 손실이 생긴다. 총 이익은 얻은 이익에서 손실을 뺀 값이다.

총 이익이 최대가 되도록 모든 길을 한 번씩 지나는 경로를 출력하시오.

첫째 줄에 N(1 <= N <= 1,000), M(1 <= M <= 100,000)이 주어진다. 다음 M개의 줄에는 i번째 길의 정보 a[i], b[i], w[i]가 주어진다. 이는 i번째 길이 a[i]번 집과 b[i]번 집을 연결한다는 뜻이다.

항상 a[i] != b[i]이며, w[i]는 8자리 이하의 자연수이다.

방문하는 순서대로 집 번호를 한 줄에 하나씩 출력한다. 마지막 줄에는 -1을 출력한다.