성공으로 가는 엘리베이터는 고장입니다. 당신은 계단을 이용해야만 합니다. 한계단 한계단씩
– 조 지라드 -

1101: [브론즈-80]다익스트라 알고리즘

Memory Limit:128 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:admin
Submit:0 Solved:0

Description

아래의 가중치 방향그래프에서 1번 정점에서 모든 정점으로의 최소 거리비용을 출력하는 프로
그램을 작성하세요. (경로가 없으면 Impossible를 출력한다)


Input

첫째 줄에는 정점의 수 N(1<=N<=20)와 간선의 수 M가 주어진다. 그 다음부터 M줄에 걸쳐 연
결정보와 거리비용이 주어진다.

Output

1번 정점에서 각 정점으로 가는 최소 비용을 2번 정점부터 차례대로 출력하세요.

Sample Input Copy

6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

Sample Output Copy

2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible