#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,x,y,z,s,nume=0;
int dist[10002],vis[10002],head[10002];
struct Edge{
	int next,to,dis;
} edge[500002];
void add(int x,int y,int d){
	edge[++nume].next=head[x];
	edge[nume].to=y;
	edge[nume].dis=d;
	head[x]=nume;
}
void SPFA(int v0){
	queue<int> q;
	memset(dist,0x3f,sizeof(dist));
	memset(vis,false,sizeof(vis));
	q.push(v0);
	dist[v0]=0;
	vis[v0]=true;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].to;
			if(dist[v]>dist[u]+edge[i].dis){
				dist[v]=dist[u]+edge[i].dis;
				if(!vis[v]){
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;++i){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	SPFA(s);
	for(int i=1;i<=n;++i) cout<<dist[i]<<" ";
return 0;
}