#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
vector<int>a[200005],w[200005];
int dis[100005];
bool pan[100005];
void dj(int s)
{
	q.push({0,s});
		
	while(!q.empty())
	{int u=q.top().second;
	q.pop();
		if(pan[u])continue;
		
		pan[u]=1;
			for(int i=0;i<a[u].size();i++)
			{		
				if((!pan[a[u][i]])&&(dis[a[u][i]]>dis[u]+w[u][i]))
				{
					dis[a[u][i]]=dis[u]+w[u][i];
					q.push( { dis[a[u][i]],a[u][i] } );
				}
			}
		
	
	}
	
}
int main()
{
int n,m,s;
cin>>n>>m>>s;
for(int i=0;i<m;i++)
{
	int o,p,l;
	cin>>o>>p>>l;
	a[o].push_back(p);
	w[o].push_back(l);
}

for(int i=0;i<=n;i++)
{
	pan[i]=0;
	dis[i]=12345678;
}
dis[1]=0;
dj(1);
for(int i=1;i<=n;i++)
{
		cout<<dis[i]<<" ";
}
return 0;
}