#include<bits/stdc++.h>
#define pii pair<int,int>
#define mpr make_pair
#define int long long
using namespace std;
const int N = 2e5+10;
int n,m,s;
struct Edge
{
	int to,nxt,w;
}e[N];
int cnt,head[N];
bool vis[N];
int dis[N];
void add(int u,int v,int w)
{
	e[++cnt].to = v;
	e[cnt].w = w;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
void dij()
{
	priority_queue<pii,vector<pii>,greater<pii> > q;
	q.push(mpr(0,s));
	for(int i=1; i<=N; i++) dis[i] = ((1ll)<<31)-1;
	dis[s] = 0; 
	memset(vis,0,sizeof(vis));
	while(!q.empty())
	{
		int x = q.top().second; q.pop();
		if(vis[x]) continue;
		vis[x] = 1;
		for(int i=head[x]; i; i=e[i].nxt)
		{
			int y = e[i].to,w = e[i].w;
			if(dis[x]+w < dis[y])
			{
				dis[y] = dis[x]+w;
				q.push(mpr(dis[y],y));
			} 
		}
	}
}
signed main()
{
	cin>>n>>m>>s; 
	
	for(int i=1; i<=m; i++)
	{
		int u,v,w; cin>>u>>v>>w;
		add(u,v,w);
	}
	dij();
	for(int i=1; i<=n; i++)
	{
		cout<<dis[i]<<" ";
	}
	return 0;	
} 

但标准版过了。。。