#include<bits/stdc++.h>
using namespace std;
const int maxm=5e5+10,maxn=1e5+10;
typedef pair<int,int> PII;
int head[maxn],id=0;
struct Node
{
	int end;int w;int next;
}edge[maxm];
int ans[maxn];
bool visit[maxn];
void init()
{
	memset(head,-1,sizeof(head));
}
void push_edge(int f,int e,int w0)
{
	if(f==e) return;
	id++;
	Node t;
	t.end=e;
	t.w=w0;
	t.next=-1;
	if(head[f]==-1)
	{
		head[f]=id;
	}
	else
	{
		int x=head[f];
		int tf=x;
		while(x!=-1) 
		{
			tf=x;
			if(edge[x].end==e)
			{
				edge[x].w=min(edge[x].w,w0);
				id--;
				return;
			}
			x=edge[x].next;
		}
		edge[tf].next=id;
	}
	edge[id]=t;
}
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
	{
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
	{
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
int main()
{
	priority_queue<PII,vector<PII>,greater<PII> >q;
	int n,m,s;
	cin>>n>>m>>s;
	init();
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		u=read();
		v=read();
		w=read();
		push_edge(u,v,w);
	}
	memset(ans,0x3f,sizeof ans);
	
	visit[s]=1;
	
	for(int x=head[s];x!=-1;x=edge[x].next)
	{
		ans[edge[x].end]=edge[x].w;
	}
	ans[s]=0;
	for(int i=1;i<=n;i++)
	{
		q.push(make_pair(ans[i],i));
	}
	
	for(int i=1;i<=n-1;i++)
	{
		pair<int,int> ss=q.top();
		while(visit[ss.second]) 
		{
			q.pop();
			ss=q.top();
		}
		
		int k=q.top().second;
		q.pop();
		visit[k]=1;
		for(int p=head[k];p!=-1;p=edge[p].next)
		{
			int e=edge[p].end;
			int w=edge[p].w;
			if(visit[e]) continue;
			ans[e]=min(ans[e],ans[k]+w);
			q.push(make_pair(ans[e],e));
		}
	
	}
	for(int i=1;i<=n;i++) 
	{
		 cout<<ans[i]<<" ";
	}
}