#include<bits/stdc++.h>
using namespace std;
struct Edge{
	long long to,nxt,w;
}a[500005];
long long h[500005],cnt;
void add(int u,int v,int w){
	a[++cnt].to=v;
	a[cnt].nxt=h[u];
	a[cnt].w=w;
	h[u]=cnt;
}
long long n,s,m;
long long dis[500005];
bool vis[500005];
void dijkstra(int u)
{
	int t=u;
	dis[u]=0;
	vis[u]=1;
	for(int AC=1;AC<=n;AC++){
//		cout<<t<<endl;
		long long minn=1e9;
		vis[t]=1;
		for(int i=h[t];i!=0;i=a[i].nxt){
			if(vis[a[i].to]==0&&dis[a[i].to]>dis[t]+a[i].w){
//				cout<<AC<<"  "<<a[i].to<<endl;
				dis[a[i].to]=dis[t]+a[i].w;
			}
		}
		for(int i=1;i<=m;i++){
			if(a[i].to&&vis[a[i].to]==0&&dis[a[i].to]<minn){
				t=a[i].to;
				minn=dis[a[i].to];
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
}

int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++){
		dis[i]=1e9;
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		add(u,v,w);	 
	}
//	for(int i=1;i<=m;i++){
//		cout<<i<<"  "<<a[i].to<<"  "<<a[i].nxt<<" "<<a[i].w<<endl;
//	}
	dijkstra(s);
	return 0;
}