#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,s;
	cin>>n>>m>>s;
	vector<pair<int,int> > rel[n];
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		rel[x-1].push_back({y,z});
	}
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > dist;
	dist.push({0,s});
	for(int i=1;i<=n;i++){
		if(i!=s) dist.push({1000000001,i});
	}
	int vis[n];
	memset(vis,0,n);
	for(int i=0;i<n-1;i++){
		vis[dist.top().second-1]=1;
		for(int j=0;j<rel[dist.top().second-1].size();j++){
			if(vis[j]==0) vis[j]=dist.top().first+rel[i][j].second;
			else vis[j]=min(vis[j],dist.top().first+rel[i][j].second);
			dist.push({dist.top().first+rel[i][j].second,j+1});
		}
		dist.pop();
	}
	for(int i=0;i<n;i++) cout<<vis[i]<<" ";
}