마을 N개와 일방통행 도로 M개가 있어요. 모든 마을 쌍 (i, j)에 대해 i에서 j로 가는 최소 비용을 표로 만드세요.
입력
첫째 줄에 N과 M이 주어져요. (1 ≤ N ≤ 100, 0 ≤ M ≤ 5,000) 다음 M줄에 u v w(u에서 v로 가는 비용 w)가 주어져요. (1 ≤ w ≤ 1,000, 같은 u v 쌍이 여러 번 나오면 가장 싼 것만 유효)
출력
N줄에 걸쳐 거리표를 출력해요. i번째 줄의 j번째 수는 i에서 j로 가는 최소 비용이에요. 자기 자신은 0, 갈 수 없으면 -1이에요.