플로이드

n(2 ≤ n ≤ 100)개의 도시가 있고, 한 도시에서 출발해 다른 도시에 도착하는 버스가 m(1 ≤ m ≤ 100,000)개 있다. 버스마다 한 번 타는 데 드는 비용이 정해져 있다.

모든 도시 쌍 (A, B)에 대해 도시 A에서 도시 B로 가는 데 드는 최소 비용을 구하는 프로그램을 작성하시오.

첫째 줄에 도시의 개수 n, 둘째 줄에 버스의 개수 m이 주어진다. 셋째 줄부터 m+2번째 줄까지 버스 정보가 한 줄에 하나씩 주어진다. 각 줄은 버스의 시작 도시 a, 도착 도시 b, 한 번 타는 데 드는 비용 c로 이루어진다. 시작 도시와 도착 도시가 같은 버스는 없다. 비용은 100,000보다 작거나 같은 자연수이다.

같은 시작 도시와 도착 도시를 잇는 노선이 하나가 아닐 수 있다.

n개의 줄을 출력한다. i번째 줄의 j번째 숫자는 도시 i에서 도시 j로 가는 데 드는 최소 비용이다. i에서 j로 갈 수 없으면 그 자리에 0을 출력한다. 한 줄에 있는 숫자는 공백 하나로 구분한다.