#include<iostream>
#include<cstring>
using namespace std;
long long f[10005],n,m,k,v[10005],head[10005],tot,dist[100005],vis[100005];
struct node{
	int next=-1,to,ver;
}tu[1000005];
void add(int x,int y,int z){
	tu[++tot].to=y;
	tu[tot].next=head[x];
	head[x]=tot;
	tu[tot].ver=z;
}
void tll(int root){
	vis[root]=1;
	dist[root]=0;
	int x=root;
	for(int g=1;g<n;g++){
		for(int i=1;i<=n;i++){
			x=min(dist[x],dist[i]);
		}
		vis[x]=1;
		for(int i=head[x];~i;i=tu[i].next){
			if(vis[i]==0){
				dist[tu[i].to]=min(dist[tu[i].to],dist[x]+tu[i].ver);
			}
		}
	}
}
int main(){
	memset(head,-1,sizeof head);
	memset(dist,0x3f3f3f3f,sizeof dist);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
	}
	tll(k);
	for(int i=1;i<=n;i++){
		cout<<dist[i]<<endl;
	}
}