#include<bits/stdc++.h>
using namespace std;
const int N=10000+10;
const int NN=100000*5;
typedef long long ll;
ll g[N][N],dis[NN],book[NN];
ll n,m,s,minn;
ll x,y,l,u,v;
int main() {
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			if(i==j) g[i][j]=0;
			else g[i][j]=2147483647;
		}
	}
	for(int i=1;i<=m;i++) {
		cin>>x>>y>>l;
		g[x][y]=l;
	}
	for(int i=1;i<=n;i++) 
		dis[i]=g[1][i];
	for(int i=1;i<=n;i++)
		book[i]=0;
	book[1]=1;
	for(int i=1;i<=n-1;i++) {
		minn=2147483647;
		for(int j=1;j<=n;j++) {
			if(book[j]==0&&dis[j]<minn) {
				minn=dis[j];
				u=j;
			}
		}
		book[u]=1;
		for(v=1;v<=n;v++) {
			if(g[u][v]<1e9) {
				if(dis[v]>dis[u]+g[u][v])
					dis[v]=dis[u]+g[u][v];
			}
		}
	}
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
	getchar();
	getchar();
	return 0;
}

一个点也不过