#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 1000010
#define oo 2147483647
struct node{
	int u,v,w,nxt;
}edge[M];
int n,m,s,dis[N],cnt=1,head[N],used[N];
void add_edge(int u,int v,int w){
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
	cnt++;
}
void dijkstra(){
	int i,j;
	dis[s]=0;
	used[s]=1;
	for(i=head[s];i!=0;i=edge[i].nxt) if(edge[i].v!=s)dis[edge[i].v]=edge[i].w;
	for(i=1;i<n;i++){
		int minn=oo,now;
		for(j=1;j<=n;j++){
			if(minn>dis[j]&&used[j]==0) minn=dis[j],now=j;
		}
		used[now]=1;
		for(j=head[now];j!=0;j=edge[j].nxt){
			if(dis[now]+edge[j].w<dis[edge[j].v])dis[edge[j].v]=dis[now]+edge[j].w;
		}
	}
}
int main(){
	int i,u,v,w;
	cin>>n>>m>>s;
	for(i=1;i<=n;i++){
		dis[i]=oo;
	}
	for(i=1;i<=m;i++){
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	dijkstra();
	for(i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 1000010
#define oo 0x7fffffff
struct node{
	int u,v,w,nxt;
}edge[M];
int n,m,s,dis[N],cnt=1,head[N],used[N];
void add_edge(int u,int v,int w){
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
	cnt++;
}
void dijkstra(){
	int i,j,minn,now;
	dis[s]=0;
	now=s;
	//for(i=head[s];i!=0;i=edge[i].nxt) if(edge[i].v!=s)dis[edge[i].v]=edge[i].w;
	for(i=1;i<=n;i++){
		for(j=head[now];j!=0;j=edge[j].nxt){
			if(dis[now]+edge[j].w<dis[edge[j].v])dis[edge[j].v]=dis[now]+edge[j].w;
		}
		used[now]=1;
		minn=oo;
		for(j=1;j<=n;j++){
			if(minn>dis[j]&&used[j]==0) minn=dis[j],now=j;
		}
	}
}
int main(){
	int i,u,v,w;
	cin>>n>>m>>s;
	for(i=1;i<=n;i++){
		dis[i]=oo;
	}
	for(i=1;i<=m;i++){
		cin>>u>>v>>w;
		add_edge(u,v,w);
	}
	dijkstra();
	for(i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}