rt

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int inf = (1 << 31) - 1;
int n,m,s;
int to[N],h[N],nxt[N],val[N],dis[N],cnt;
bool vis[N];
queue <int> q;
void spfa()
{
	for(int t = 1;t <= n;t++)
	{
		dis[t] = inf;
	}
	dis[s] = 0;
	vis[s] = 1;
	q.push(s);
	while(!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = h[u];i;i = nxt[i])
		{
			if(dis[to[i]] > (long long) dis[u] + val[i])
			{
				dis[to[i]] = dis[u] + val[i];
				if(!vis[to[i]])
				{
					q.push(to[i]);
					vis[to[i]] = 1;
				}
			}
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	for(int t = 1;t <= m;t++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		to[++cnt] = v;
		val[cnt] = w;
		nxt[cnt] = h[u];
		h[u] = cnt;	
	}
	spfa();
	for(int t = 1;t <= n;t++)
	{
		cout << dis[t] << " ";
	}
	return 0;
}