철도 건설

당신의 카운티가 가장 큰 두 도시인 Acmar와 Ibmar를 잇는 철도 시스템을 놓기 위한 주(州) 보조금을 받게 되었다. 이 철도 시스템은 여러 개의 구간으로 나뉘어 건설된다. 각 구간은 서로 다른 두 도시를 잇고, 첫 번째 구간은 Acmar에서 시작하며, 마지막 구간은 Ibmar에서 끝난다.

보조금 규정은 다음과 같다. 주는 철도 시스템에서 가장 비싼 두 구간의 비용을 내고, 카운티는 나머지 구간의 비용을 모두 낸다.

• 철도 시스템이 구간을 두 개만 가지면, 주는 그 둘 중 더 비싼 구간 하나만 낸다.
• 철도 시스템이 구간을 하나만 가지면, 주는 아무것도 내지 않는다.

주는 단순 경로, 즉 어떤 도시도 두 번 이상 방문하지 않는 경로만 고려한다.

여러 도시 쌍을 잇는 비용의 견적이 주어질 때, 카운티가 내는 비용이 가능한 한 적어지도록 철도 시스템을 어떻게 건설할지 정하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 케이스는 구간 비용 견적의 개수를 나타내는 하나의 양의 정수 $n \le 50$이 있는 줄로 시작한다. (모든 도시 쌍에 대해 견적이 있는 것은 아니다.) 그 뒤로 $n$개의 줄에 각각 하나의 견적이 세 정수 s e c로 주어지며, 이는 도시 $s$와 $e$를 잇는 구간을 건설하는 데 드는 예상 비용이 $c$임을 뜻한다.

Acmar는 항상 도시 $0$이고 Ibmar는 항상 도시 $1$이며, 나머지 도시는 연속된 정수로 번호가 매겨진다. 비용은 대칭적이며($s$에서 $e$로 잇는 비용과 $e$에서 $s$로 잇는 비용이 같다), 항상 양수이고 $1000$ 이하이다. 이 구간들을 이용해 Acmar에서 Ibmar까지 철도로 이동하는 것은 항상 가능하다. $n = 0$인 줄이 입력의 끝을 나타낸다.

각 테스트 케이스에 대해, 다음 형식의 한 줄을 출력한다.

c1 c2 ... cm cost

여기서 $c_1, c_2, \ldots, c_m$은 가장 저렴한 경로를 이루는 도시들을 순서대로 나열한 것이고, cost는 카운티가 내는 비용이다. $c_1$은 항상 $0$(Acmar), $c_m$은 항상 $1$(Ibmar)이며, 연속한 두 도시 $c_i$와 $c_{i+1}$은 경로 위에서 하나의 구간으로 연결되어 있다.

카운티가 내는 비용이 같은 경로가 여럿이면 구간 수가 가장 적은 경로를 출력하고, 그래도 같으면 사전순으로 가장 앞선 경로를 출력한다.