#include<bits/stdc++.h>
using namespace std;
const long long maxn=pow(2,31)-1;
int n,m,s;
int dis[10001];
struct node{
	int u,v;
	int l;
}p[500005]; //每个边 
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int uu,vv,ll;
		cin>>uu>>vv>>ll;
		p[i].u=uu;
		p[i].v=vv;
		p[i].l=ll;
	}
	for(int i=1;i<=n;i++)
	    dis[i]=maxn;
	dis[s]=0;
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=m;j++){
			int nowu=p[j].u,nowv=p[j].v,nowl=p[j].l;
			dis[nowv]=min(dis[nowv],dis[nowu]+nowl);
		}
	}
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	
	return 0;
}