#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n,m,s;
vector<pair<int, int> > vec[maxn];
int b[maxn];
int minn = INT_MAX;
int dis[maxn];
bool vis[maxn];
priority_queue<int> q;
void add(int u, int v, int w)
{
	vec[u].push_back(make_pair(v, w));
}
int main()
{
	cin>>n>>m>>s;
	for(int i = 1; i <= m; i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x, y, z);
	}
	for(int i = 1; i <= n; i++)
		dis[i]=INT_MAX;
	q.push(s);
	dis[s] = 0;
	while(!q.empty())
	{
		int u = q.top();
		q.pop();
		if(vis[u])
			continue;
		vis[u] = true;
		for(auto p : vec[u])
		{
			int v = p.first;
			int w = p.second;
			if(dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if(!vis[v])
					q.push(v);
			}
		}
	}
	for(int i = 1; i <= n; i++)
		cout<<dis[i]<<' ';
	return 0;
}