1968번 - 우체부 스페셜 저지

N개의 집들로 이루어진 작은 마을이 있다. 집들 중, 몇 개는 길로 연결되어 있다. 각각의 길의 가운데에 우체통이 하나씩 있어서 마을 사람들은 이 우체통을 이용한다.

이 마을에는 우체부가 한 명 있는데, 이 우체부가 길들을 돌아다니며 우체통 안의 우편물을 수거한다. 이 우체부는 한 번 갔던 길을 다시 방문하는 비효율적인 일을 하려 하지 않는다. 다행히도, 이 마을의 구조상 한 번 갔던 길을 다시 지나지 않으면서 모든 길을 지나는 방법이 항상 존재한다.

우체부는 이러한 방법을 찾아낸 뒤, 매번 같은 경로를 이용하여 우편물을 모으고 있었다. 그러다보니 매번 우편물들이 똑같은 순서로 모이게 되었는데, 우편물들의 우선순위가 다를 때도 우편물들이 같은 순서로 모이는 비효율적인 현상이 발생하게 되었다.

이에 마을 사람들은 다음과 같은 방법을 동원하기로 하였다. 각각의 우체통에는 w[i]라는 가중치가 있는데, 이 우체통이 우체부가 k번째로 지나는 우체통이라 하자. 만약 w[i]보다 k가 작다면 우체부는 w[i]-k의 수익을 얻는다. 반면에 w[i]가 k보다 크다면 우체부는 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을 출력한다.