주행 거리

요즘 많은 자동차 회사들이 휘발유 대신 전기로 달리는 자동차를 개발하고 있다. 이런 자동차에 쓰이는 배터리는 대체로 매우 무겁고 비싸기 때문에, 설계자들은 배터리 용량과 그에 따른 주행 거리를 정할 때 중요한 절충을 해야 한다. 여러분이 할 일은, 대륙의 임의의 두 도시 사이를 오갈 수 있도록 하는 데 필요한 최소 주행 거리를 구하는 것이다.

대륙의 도로망은 서로 다른 길이의 양방향 도로로 연결된 도시들로 이루어져 있다. 각 도시에는 충전소가 있다. 두 도시 사이의 경로에서 자동차는 임의의 개수의 도시를 거쳐 갈 수 있지만, 경로를 따라 이웃한 두 도시 사이의 거리는 자동차의 주행 거리보다 길어서는 안 된다. 대륙의 모든 도시 쌍 사이에 이 조건을 만족하는 경로가 존재하도록 하는 자동차의 최소 주행 거리는 얼마인가?

입력은 여러 개의 도로망으로 이루어진다. 각 도로망의 첫 줄에는 두 정수 $n$과 $m$, 즉 도시의 수와 도로의 수가 주어진다. 두 정수는 각각 백만 이하이다. 도시는 $0$부터 $n-1$까지 번호가 매겨진다. 첫 줄 다음에는 $m$개의 줄이 이어지며, 각 줄은 하나의 도로를 나타낸다. 각 줄에는 세 개의 음이 아닌 정수가 주어지는데, 앞의 두 정수는 그 도로가 연결하는 두 도시의 번호이고, 세 번째 정수는 그 도로의 길이이다.

마지막 도로망 다음에는 $0$이 두 개 적힌 줄이 주어지며, 이는 입력의 끝을 의미한다.

각 도로망에 대해, 모든 도시에서 다른 모든 도시로 갈 수 있게 하는 자동차의 최소 주행 거리를 정수 하나로 한 줄에 출력한다. 만약 주행 거리와 상관없이 어떤 도시에서 다른 어떤 도시로 갈 수 없다면, 대신 IMPOSSIBLE이라는 단어를 한 줄에 출력한다.