군중 통제

프로그래밍 대회 때문에 암스테르담에 많은 방문객이 모인다. 이 사람들은 대부분 기차역에 도착한 뒤, 거리를 따라 교차로에서 교차로로 이동하는 큰 행렬을 이루어 대회장까지 걸어간다.

거리마다 한 시간에 지나갈 수 있는 사람 수가 정해져 있고, 이 값을 그 거리의 용량이라고 한다. 어떤 거리를 지나가는 사람 수가 그 거리의 용량을 넘으면 사고가 나므로 절대 넘어서는 안 된다. 거리는 양쪽 방향 모두로 걸을 수 있다.

주최 측은 기차역에서 대회장까지 이어지는 경로를 하나만 준비한다. 경로의 용량은 그 경로에 속한 거리의 용량 중 최솟값이고, 주최 측은 용량이 가장 큰 경로를 고른다. 아무도 엉뚱한 방향으로 가지 않도록, 경로 위의 교차로를 한쪽 끝점으로 가지면서 경로에는 속하지 않는 거리를 모두 막는다.

암스테르담의 거리와 교차로가 이루는 그래프가 주어진다. 기차역에서 대회장까지 용량이 최대인 경로 하나를 만들려면 어떤 거리를 막아야 하는지 출력하는 프로그램을 작성하라. 경로는 단순해야 한다. 즉 같은 교차로를 두 번 지날 수 없다.

첫 줄에 도시의 교차로 수 $n$과 거리 수 $m$이 주어진다 ($1 \le n, m \le 1000$).

이어지는 $m$개 줄에는 거리 정보가 한 줄에 하나씩 주어진다. 각 줄에는 세 정수 $a_i$, $b_i$, $c_i$가 주어지는데, $a_i$와 $b_i$는 이 거리가 잇는 두 교차로의 번호이고 ($0 \le a_i, b_i < n$), $c_i$는 이 거리의 용량이다 ($1 \le c_i \le 500000$). 거리에는 주어진 순서대로 $0$번부터 $m - 1$번까지 번호가 붙는다.

입력은 항상 다음을 만족한다.

• 모든 방문객은 $0$번 교차로인 기차역에서 출발하고, 대회장은 $n - 1$번 교차로에 있다.
• 교차로와 거리는 연결 그래프를 이룬다.
• 같은 교차로 쌍을 잇는 거리가 둘 이상 존재하지 않는다.
• 양 끝점이 같은 교차로인 거리는 없다.
• 용량이 최대인 단순 경로는 유일하다.

기차역에서 대회장까지 용량이 최대인 경로 하나만 남기려면 막아야 하는 거리의 번호를 공백으로 구분해 한 줄에 출력한다. 번호는 증가하는 순서로 정렬한다.

막아야 하는 거리가 하나도 없으면 대신 none을 출력한다.

첫 번째 예제 입력을 나타낸 그림이다.