문제 설명
미술관에는 전시실이 N개 있다. 각 전시실에는 1~N까지 번호가 차례대로 붙어 있다.
이때 i 전시실에서 j 전시실로 이동하는 통로가 있고, 이동하는 데 m이 걸린다고 할 때 해당 경로에 대한 정보를 다음과 같이 표현한다.
i j m
이 때 모든 전시실을 방문하는 데 걸리는 최소 시간을 구해보자.
단, 방문했던 전시실을 다시 방문하지 않아야 한다.
이때 i 전시실에서 j 전시실로 이동하는 통로가 있고, 이동하는 데 m이 걸린다고 할 때 해당 경로에 대한 정보를 다음과 같이 표현한다.
i j m
이 때 모든 전시실을 방문하는 데 걸리는 최소 시간을 구해보자.
단, 방문했던 전시실을 다시 방문하지 않아야 한다.
입력 설명
전체 전시실의 수(N)와 통로의 수(M)가 입력된다.
M줄에 걸쳐 통로로 연결된 두 전시실의 번호와 이동하는 데 걸리는 시간이 공백으로 구분되어 입력된다.
M줄에 걸쳐 통로로 연결된 두 전시실의 번호와 이동하는 데 걸리는 시간이 공백으로 구분되어 입력된다.
출력 설명
최소 시간을 출력한다. 만약 경로가 없다면 Impossible을 출력한다.
입력 예시 Copy
7 11
1 2 2
1 3 7
1 4 5
1 7 6
2 3 9
3 7 3
4 5 3
4 6 6
4 7 7
5 6 3
6 7 7
출력 예시 Copy
23