#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+5;
priority_queue<pair<int,int>>q;
int n,m,a[MAXN],s,d[MAXN];
bool vis[MAXN];
vector<pair<int,int>>v[MAXN];
int main()
{
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++) d[i]=INT_MAX;
	for(int i=1;i<=m;i++)
	{
		int from,to,len;
		cin>>from>>to>>len;
		v[from].push_back(make_pair(to,len));
	}
	d[1]=0;
	q.push(make_pair(0,1));
	while(q.size())
	{
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=0;i<v[x].size();i++)
		{
			int k=v[x][i].first,y=v[x][i].second;
			if(d[k]>d[x]+y)
			{
				d[k]=d[x]+y;
				q.push(make_pair(-d[k],k));
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<d[i]<<" ";
	}
	return 0;
}