#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=10010;
struct Edge{
	int toward,to,len;
}edge[500010];
int numedge,dot[N];
int q[N],l=1,r=1;
bool vis[N];
int dis[N];
void add(int from,int to,int len)
{
	edge[++numedge].toward=dot[from];
	edge[numedge].to=to;
	dot[from]=numedge;
	edge[numedge].len=len;
}
void SPFA()
{
	
	while(l<=r)
	{
		int b;
		b=q[l];
		for(int i=dot[b];i;i=edge[i].toward)
		{
			int h=edge[i].to;
			int k=edge[i].len;
			dis[h]=min(dis[h],dis[b]+k);
			if(vis[h]==0) {
				q[++r]=h;
				vis[h]=1;
			}
		}
		l++; 
	}
}
int main()
{
	int n,m,s;
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		add(a,b,c);
	}
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[s]=0;
	q[1]=s;
	vis[s]=1;
	SPFA();
	for(int i=1;i<=n;i++)
	if(dis[i]==0x3f3f3f3f) cout<<2147483647<<' ';
	else printf("%d ",dis[i]);
	
	return 0;
 }