#include <bits/stdc++.h>
using namespace std;
int w[1000000];
int e[1000000];
int head[1000000];
int nxt[1000000];
int cnt;//第i条边 
int dis[1005][1005];
int n,m,s;
void addEdge(int a,int b,int c){//连线函数 
	cnt++;
	e[cnt] = b;
	w[cnt] = c;
	nxt[cnt] = head[a]; 
	head[a] = cnt;
	dis[a][b] = c;//设置a->b的最短路径为c 
}
int main(){
	memset(dis,0x7f,sizeof(dis));//设置所有点距离为无穷大 
	cin >> n >> m >> s;
	for(int i = 1;i<=m;i++){//建图 
		int x,y,z;
		cin >> x >> y >> z;
		addEdge(x,y,z);
	}
	for(int k = 1;k<=n;k++){//弗洛伊德
		for(int i = 1;i<=n;i++){
			for(int j = 1;j<=n;j++){
				dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	for(int i = 1;i<=n;i++){//输出 
		for(int j = 1;j<=n;j++){
			if(dis[i][j] == 0x7f7f7f7f){
				cout << -1 << " ";
			}else{
				cout << dis[i][j] << " ";
			}
		}
		cout << endl;
	}
}