#include<bits/stdc++.h>
using namespace std;
#define int long long
int dis[100010],book[100010];
vector <int > v[200010][10];
struct node{
	int p,zhi;
};
bool  operator <(node n1,node n2){
	return n1.zhi >n2.zhi;
}
priority_queue<node> q;
signed main(){
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v1,w;
		cin>>u>>v1>>w;
		v[u][1].push_back(v1);
		v[u][2].push_back(w);
	}
	for(int i=1;i<=n;i++){
		dis[i]=0x7ffffff;
	}
	dis[s]=0;
	
	/*for(int j=0;j<v[s][1].size();j++){
		int yy=v[s][1][j];
			dis[yy]=min(dis[yy],dis[s]+v[s][2][j]);q.push({yy,dis[yy]});
		}*/q.push({s,0});
	while(q.size()>0){
		node n1=q.top();
		q.pop();
		int hhh=n1.p;
		/*for(int j=1;j<=n;j++){
			if(dis[j]!=0x7ffffff&&book[j]!=1){
			jjj=min(dis[n],jjj);
			if(jjj==dis[n]){
				hhh=n;
			}
			}
			
		}*/
		if(book[hhh]==1) continue;
		book[hhh]=1;
		for(int j=0;j<v[hhh][1].size();j++){
			int hh=v[hhh][1][j];
			dis[hh]=min(dis[hh],dis[hhh]+v[hhh][2][j]);
			q.push({hh,dis[hh]});
		}
	}	
	
	for(int i=1;i<=n;i++){
 cout<<dis[i]<<' ';
}
return 0;
}