항로 운임표

한 해운 회사는 항구 n곳을 오가는 화물 항로를 운영한다. 항구에는 1번부터 n번까지 번호가 붙어 있다.

항로는 모두 m개다. 각 항로마다 출발 항구와 도착 항구, 그리고 그 항로를 한 번 쓸 때 드는 운임이 정해져 있다. 항로는 한쪽 방향으로만 운항한다. A번 항구에서 B번 항구로 가는 항로가 있다고 해서 B번 항구에서 A번 항구로 가는 항로도 있는 것은 아니다.

같은 두 항구를 잇는 항로가 여러 개일 수도 있다. 이 경우 항로마다 운임이 다를 수 있으므로 그 가운데 어느 것을 골라 써도 된다.

화물은 중간 항구를 몇 군데든 거쳐 갈 수 있다. 어떤 항구에서 다른 항구로 화물을 보낼 때 드는 운임은 거쳐 간 모든 항로의 운임을 더한 값이다. 회사는 항구마다 다른 모든 항구로 화물을 보낼 때 드는 운임의 최솟값을 적은 표를 만들려고 한다.

모든 항구 쌍에 대하여 A번 항구에서 B번 항구로 화물을 보내는 데 드는 운임의 최솟값을 계산하는 프로그램을 작성하여라. A번 항구에서 B번 항구로 가는 길이 아예 없다면 그 자리에는 0을 적는다. 또한 A와 B가 같은 항구인 자리에도 0을 적는다.

예를 들어 n=5, m=8인 상황을 가정하자. 각 항로에 대한 정보가 다음의 표와 같다고 해보자.

3번 항로와 7번 항로는 둘 다 4번 항구에서 1번 항구로 가는 항로인데 운임이 654와 85234다. 이때는 더 싼 654를 쓰면 된다. 4번 항로와 8번 항로도 마찬가지로 둘 다 1번 항구에서 4번 항구로 가며, 더 싼 43709를 쓰면 된다.

2번 항구와 3번 항구에서 출발하는 항로는 하나도 없다. 그래서 두 항구에서는 다른 어떤 항구로도 화물을 보낼 수 없다.

현재 예시에서 모든 항구 쌍에 대한 운임의 최솟값을 표로 정리하면 다음과 같다.

표에서 몇 자리를 짚어 보자. 1번 항구에서 3번 항구로 바로 가는 2번 항로의 운임은 88309다. 그런데 1번 항구에서 5번 항구로 가는 27284를 쓰고 이어서 5번 항구에서 3번 항구로 가는 29349를 쓰면 합이 56633이므로 이쪽이 더 싸다. 1번 항구에서 2번 항구로 가는 길은 4번 항구를 거치는 것뿐이며 43709와 72425를 더한 116134다.

입출력 예시

예시 1

입력

5
8
5 3 29349
1 3 88309
4 1 654
1 4 49215
1 5 27284
4 2 72425
4 1 85234
1 4 43709

출력

0 116134 56633 43709 27284 
0 0 0 0 0 
0 0 0 0 0 
654 72425 57287 0 27938 
0 0 29349 0 0 

예시 2

입력

3
3
2 3 82322
2 3 40264
2 3 18432

출력

0 0 0 
0 0 18432 
0 0 0 

예시 3

입력

1
0

출력

0