#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
#define ll long long
#define INF 2147483647 
using namespace std;
ll n,m,s,cnt=0;
ll to[50010],nxt[50010],val[50010],h[50010],dis[50010],v[50010];
struct node{
	ll v,w;
	friend int operator <(node a,node b)
	{
		return a.w>b.w;
	}
}tmp;
priority_queue<node> q;
void add(int u,int v,int num)
{
	to[++cnt]=v,val[cnt]=num,nxt[cnt]=h[u],h[u]=cnt;
}
void dijkstra()
{
	for(int i=0;i<=n;i++)dis[i]=INF;
	dis[s]=0;
	tmp.v=s,tmp.w=0;
	q.push(tmp);
	while(!q.empty())
	{
		int u=q.top().v;
		q.pop();
		if(v[u])continue;
		v[u]=1;
		for(int i=h[u];i;i=nxt[i])
		{
			if(dis[to[i]]>dis[u]+val[i])
			{
				dis[to[i]]=dis[u]+val[i];
				tmp.w=dis[to[i]],tmp.v=to[i];
				q.push(tmp);
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	dijkstra();
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}