'가장 짧은' 경로 쌍

어느 화학 회사에 특이한 최단 경로 문제가 있습니다.

화학 물질을 보관할 수 있는 $N$개의 창고(정점)가 있고, 창고 쌍을 잇는 $M$개의 개별 운송 수단(간선)이 있습니다. 각 운송 수단에는 비용이 있습니다. 보통의 문제라면 회사는 첫 번째 창고($0$)에서 마지막 창고($N - 1$)로 화물 하나만 보내면 되고, 이는 쉽습니다. 그런데 이 회사의 문제는 더 어렵습니다. 두 가지 화학 물질을 첫 번째 창고($0$)에서 마지막 창고($N - 1$)로 보내야 합니다. 이 화학 물질들은 위험해서 함께 둘 수 없습니다. 규정에 따르면 두 물질에 대해 같은 운송 수단을 사용할 수 없습니다. 또한 특수 보관 처리 없이는 두 물질을 같은 창고에 (아무리 짧은 시간이라도) 함께 둘 수 없으며, 이러한 처리는 첫 번째와 마지막 창고에서만 가능합니다.

먼저 회사는 이러한 제약 아래에서 두 물질을 모두 보내는 것이 가능한지 알아야 합니다. 그다음에는 두 물질을 첫 번째 창고에서 마지막 창고로 보내는 최소 비용을 구해야 합니다. 요컨대, 첫 번째 창고에서 마지막 창고로 가는, 전체 비용이 최소가 되는 완전히 분리된 두 경로가 필요합니다.

여러분의 프로그램은 그 최소 비용을 구하거나, 불가능하다면 운송을 할 수 없음을 분명히 밝히면 됩니다.

입력은 여러 개의 케이스로 이루어집니다. 각 케이스의 첫 줄에는 $N$과 $M$이 주어지며, $N$은 창고의 수, $M$은 개별 운송 수단의 수입니다. $N$은 $64$보다 작고 $M$은 $10000$보다 작다고 가정해도 됩니다. 이어지는 $M$개의 줄에는 각각 세 값 $i$, $j$, $v$가 주어지며, 각 줄은 하나의 고유한 운송 수단을 나타냅니다. $i$와 $j$는 두 창고의 인덱스이고 $v$는 $i$에서 $j$로 가는 (음이 아닌 정수) 비용입니다. 이 운송 수단들은 방향이 있습니다. 즉 $i$에서 $j$로 비용 $10$에 보낼 수 있다는 사실이 $j$에서 $i$로 보내는 것에 대해서는 아무것도 말해 주지 않습니다. 또한 어떤 두 창고 사이에 운송 방법이 여러 개 있을 수 있으며, 이 점이 여기서 중요할 수 있습니다. 두 개의 $0$으로 이루어진 줄은 데이터의 끝을 의미하며 처리하지 않아야 합니다.

각 케이스마다 Instance #k: C 형태로 한 줄을 출력합니다. 여기서 $k$는 ($1$부터 시작하는) 케이스 번호이고 $C$는 두 화학 물질을 모두 보내는 최소 총비용입니다. 운송이 불가능하면 대신 Instance #k: Not possible을 출력합니다. 콜론 뒤에는 공백이 두 개 있음에 유의하세요.