#include<bits/stdc++.h>
using namespace std;
struct Edge{
	int next,to,w;
}edge[500005];
int cnt=0,n,m,tn,tt,tw,head[10001],p[10001],_n;
bool vis[10001];
void add(int next,int t,int w)
{
	edge[cnt].w=w;
	edge[cnt].to=t;
	edge[cnt].next=head[next];
	head[next]=cnt;
	cnt++;
}
struct cmp{
	template <typename T,typename U>
	bool operator()(T const &left,U const &right)
	{
		if(left.first>right.first)return true;
		else if(left.first==right.first)return left.second>right.second;
		else return false;
	}
};
priority_queue<pair<int,int>,vector<pair<int,int> >,cmp>q;
int main()
{
	memset(head,-1,sizeof(head));
	memset(vis,false,sizeof(vis));
	memset(p,0x3f,sizeof(p));
	cin>>n>>m>>_n;
	for(int i=0;i<m;i++)
	{
		cin>>tn>>tt>>tw;
		add(tn,tt,tw);
	}
	p[_n]=0;
	q.push(make_pair(0,_n));
	while(!q.empty())
	{
		pair<int,int>a=q.top();
		q.pop();
		int u=a.second;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=head[u];i!=-1;i=edge[i].next)
		{
			if(p[edge[i].to]>p[u]+edge[i].w)
            {
            	p[edge[i].to]=p[u]+edge[i].w;
            	q.push(make_pair(p[edge[i].to],edge[i].to));
            }
		}
	}
	for(int i=1;i<=n;i++)
    {
        if(p[i]==int(0x3f))cout<<2147483647<<" ";
        else cout<<p[i]<<" ";
    }
	return 0;
}