#include<bits/stdc++.h>
using namespace std;
const int MAX=1000005;
typedef pair <int,int> PII;
priority_queue <PII,vector<PII>,greater<PII> > q;
int net[MAX],ver[MAX],head[MAX],edge[MAX],dist[MAX],st[MAX],n,m,tot;
void add(int a,int b,int c)
{
	net[++tot]=head[a];
	head[a]=tot;
	ver[tot]=b;
	edge[tot]=c;
}
int dijstla(int a)
{
	memset(dist,0x3f,sizeof(dist));
	dist[a]=0;
	q.push({0,a});
	while(!q.empty())
	{
		PII temp=q.top();
        q.pop();
        int v1=temp.second;
        if(st[v1])
            continue;
        st[v1]=1;
        for(int i=head[v1];i;i=net[i])
        {
            int v=ver[i];
            if(dist[v]>dist[v1]+edge[i])
            {
                dist[v]=dist[v1]+edge[i];     
                q.push({dist[v],v});
            }
        }
	}
	for(int i=1;i<=n;i++)
	if(dist[i]!=0x3f3f3f3f)cout<<dist[i]<<" ";
	else cout<<(1<<31)-1<<" ";
}
int main()
{
	int a,b,c,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		add(a,b,c);
	}
	dijstla(s);
	return 0;
}