나데르 샤

나데르 샤 아프샤르는 이란에서 가장 강력한 통치자 중 한 명이었다. 그는 헤라트 전투, 미흐만두스트 전투, 키르쿠크 전투 등 여러 전투에서 승리했다. 그의 통치 기간 동안 마슈하드는 이란의 수도였다. 그는 매년 새로운 나라를 공격하여 이란의 영토에 병합했다. 나데르 샤의 과거 승리가 모두에게 알려져 있었기 때문에, 공격받은 나라는 전투 없이 항복했다. 따라서 몇 년 후, 이란의 영토는 n개의 새로운 나라로 확장되었다.

나라들 사이에는 연결된 도로망이 있었다. 모든 도로는 양방향으로 통행할 수 있었다. 나데르 샤는 당시 이란의 영토에 적어도 하나의 도로가 연결된 나라만 공격했다. 각 나라를 점령한 후, 나데르 샤는 점령한 나라와 당시 이란의 영토 사이의 도로 중 정확히 하나를 선택하고, 1킬로미터마다 이란 국기를 꽂았다. 비용을 최소화하기 위해 그는 이란 국기가 덜 필요하므로 가장 짧은 도로를 선택했다(가장 짧은 도로가 여러 개면 그중 하나를 임의로 선택했다). 이 도로들을 아프샤리 도로라고 불렀다. 이렇게 도로를 선택하면 이란의 영토가 k개의 나라로 이루어져 있을 때 아프샤리 도로는 정확히 k - 1개이다.

몇 년 후, 우리는 나데르 샤가 죽을 때의 이란 영토 지도를 받았다. 지도에는 모든 도로망이 길이(킬로미터)와 함께 표시되어 있다. 아프샤리 도로는 지도에 표시되어 있다. 지도에는 n개의 나라, 이들을 잇는 m개의 도로가 있고, 그중 n - 1개가 아프샤리로 표시되어 있다. 각 나라는 서로 다른 번호 1 ≤ x ≤ n으로 표시되어 있다. 우리는 번호와 나라를 구별하지 않는다.

위에서 설명한 지도가 주어졌을 때, 우리는 이란에 해당하는 나라와 나데르 샤가 나라를 점령한 순서를 알고 싶다. 가능한 답 중 하나는 a1, a2, ..., an으로 나타낼 수 있는데, a1은 이란, a2는 나데르 샤가 처음 점령한 나라, a3는 두 번째로 점령한 나라, 이런 식이다. 우리는 사전순으로 가장 작은 가능한 답을 알고 싶다. 배열 x1, x2, ..., xn이 y1, y2, ..., yn보다 사전순으로 작다는 것은, (x1 = y1) ∧ (x2 = y2) ∧ ... ∧ (xi-1 = yi-1)이고 xi < yi인 수 i (1 ≤ i ≤ n)가 존재한다는 것이다.

입력의 첫 줄에는 두 정수 n과 m(1 ≤ n ≤ 1,000, n - 1 ≤ m ≤ 5,000)이 주어지는데, n과 m은 각각 지도(도로망)에 있는 나라의 수와 도로의 수이다. 다음 m개의 줄에는 도로망이 주어지며, 각 줄에는 네 정수 u, v, w, r(1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^6, r ∈ {0, 1})이 주어지는데, u와 v 사이에 길이 w킬로미터인 도로가 있고, r은 그 도로가 아프샤리인지 여부를 나타낸다. 도로는 r = 1일 때만 아프샤리이다. 두 나라 사이에는 도로가 최대 하나만 있다. 도로망에는 아프샤리 도로가 정확히 n - 1개 있고, 이 n - 1개의 도로를 통해 n개의 나라가 모두 연결되어 있음이 보장된다.

문제에 대한 답이 없으면 Wrong Map!을 출력한다. 그렇지 않으면 문제의 사전순으로 최소인 답을 출력한다.