多源最短路floyd
import java.util.Scanner;
public class Main{
static int m,n,u,v,w;
static final int N=150;
static final int INF=0x3f3f3f3f;
static long[][] g=new long[N][N];
static void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(g[i][j]>g[i][k]+g[k][j]){
g[i][j]=g[i][k]+g[k][j];
}
}
}
}
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
n=cin.nextInt();
m=cin.nextInt();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=i==j?0:INF;
}
}
while(m-->0){
u=cin.nextInt();
v=cin.nextInt();
w=cin.nextInt();
if(w<g[u][v]){
g[u][v]=g[v][u]=w;
}
}
floyd();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(j!=1){
System.out.print(" ");
}
System.out.print(g[i][j]);
}
System.out.println();
}
}
}