Let dist[i][j] be the shortest known cost from city i to city j. Initially, the only known routes are staying in the same city (cost zero) and the direct bus routes. If several routes have the same endpoints, keep only the cheapest one.
Process each city k as a possible intermediate stop. When considering k, dist[i][j] is the shortest route from i to j whose intermediate cities are among those already processed. The new best route either does not use k, or consists of a route from i to k followed by one from k to j; thus update with dist[i][k] + dist[k][j]. Skip the addition when either part is unreachable so the infinity sentinel is never added to a distance. After all intermediate cities have been processed, every shortest route is represented.
There are three nested loops over the N cities, so the time complexity is O(N^3). The distance matrix uses O(N^2) space. A long matrix and a large sentinel safely represent unreachable pairs and path sums. The required output uses 0 for pairs with no route.
import java.io.*;
import java.util.*;
public class Main {
static class FastScanner {
private final InputStream input;
private final byte[] buffer = new byte[1 << 16];
private int length = 0;
private int pointer = 0;
FastScanner(InputStream input) {
this.input = input;
}
private int read() throws IOException {
if (pointer == length) {
length = input.read(buffer);
pointer = 0;
if (length == -1) return -1;
}
return buffer[pointer++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner(System.in);
int n = input.nextInt();
int m = input.nextInt();
long infinity = Long.MAX_VALUE / 4;
long[][] dist = new long[n][n];
for (int i = 0; i < n; i++) {
Arrays.fill(dist[i], infinity);
dist[i][i] = 0;
}
for (int i = 0; i < m; i++) {
int from = input.nextInt() - 1;
int to = input.nextInt() - 1;
long cost = input.nextInt();
dist[from][to] = Math.min(dist[from][to], cost);
}
for (int mid = 0; mid < n; mid++) {
for (int from = 0; from < n; from++) {
if (dist[from][mid] == infinity) continue;
for (int to = 0; to < n; to++) {
if (dist[mid][to] == infinity) continue;
dist[from][to] = Math.min(
dist[from][to], dist[from][mid] + dist[mid][to]);
}
}
}
StringBuilder output = new StringBuilder();
for (int from = 0; from < n; from++) {
for (int to = 0; to < n; to++) {
if (to > 0) output.append(' ');
output.append(dist[from][to] == infinity ? 0 : dist[from][to]);
}
output.append('\n');
}
System.out.print(output);
}
}