택배

택배 회사에는 여러 집하장이 있다. 일부 집하장 쌍 사이에는 화물을 옮길 수 있는 양방향 경로가 있고, 각 경로에는 이동 시간이 정해져 있다.

서로 다른 두 집하장마다, 화물을 최단 시간으로 보내려면 처음으로 어느 집하장에 보내야 하는지 경로표로 정리하려고 한다. 경로표의 행은 출발 집하장, 열은 도착 집하장을 뜻한다. r행 c열의 값이 x라면, r번 집하장에서 c번 집하장으로 가는 최단 경로에서 첫 이동은 x번 집하장이어야 한다.

모든 집하장 쌍에 대한 경로표를 출력하는 프로그램을 작성하시오.

첫째 줄에 두 정수 n과 m이 주어진다.

• n은 집하장의 개수이며 1 <= n <= 200이다.
• m은 집하장 사이의 양방향 경로 개수이며 1 <= m <= 10000이다.

다음 m개의 줄에는 세 정수 a, b, t가 주어진다. 이는 a번 집하장과 b번 집하장 사이를 시간 t에 오갈 수 있다는 뜻이다. 집하장 번호와 이동 시간은 모두 1000 이하의 자연수이다.

n개의 줄에 경로표를 출력한다. i번째 줄의 j번째 값은 i번 집하장에서 j번 집하장으로 가는 최단 경로에서 처음으로 거쳐야 하는 집하장 번호이다. i = j이면 -를 출력한다. 한 줄의 값들은 공백 하나로 구분한다.