P4779

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
#define fr(i,a,b) for(ll i=a;i<=b;i++)
#define dr(i,a,b) for(ll i=a;i>=b;i--)
#define gc(c) c=getchar()
#define pc(c) putchar(c)
#define ll int
ll read()
{
	ll x=0;char c;bool flag=false;gc(c);
	while(c>'9'||c<'0'){if(c=='-')flag=true;gc(c);}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),gc(c);
	return flag? ~x+1 : x;
}
void pr(ll x)
{
	if(x<0)pc('-'),x=-x;
	if(x>9)pr(x/10);
	pc(x%10+48);
}
const int N=1e5+5,M=2e5+5;
struct edge{int to,w;};
std::vector<edge> G[N];
void add(int u,int v,int w)
{
	G[u].push_back((edge){v,w});
}
int n,m,s;
int dis[N];
bool vis[N];
typedef pair<int,int> pii;
priority_queue<pii>q;
void dijstra(int s)
{
	fr(i,1,n)dis[i]=INT_MAX,vis[i]=0;
	dis[s]=0;q.push(make_pair(0,s));vis[s]=1;
	while(!q.empty())
	{
		int u=q.top().second;q.pop();
		for(edge e:G[u])
		{
			int v=e.to,w=e.w;
			if(vis[v])continue;
			if(dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v)),vis[v]=1;
			}
		}
	}
}
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	n=read();m=read();s=read();
	for(int i=1,u,v,w;i<=m;i++)
	{
		u=read();v=read();w=read();
		add(u,v,w);
	}
	dijstra(s);
	for(int i=1;i<=n;i++)pr(dis[i]),pc(' ');
//	fclose(stdout);
	return 0;
}