#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
int n,m,s,x,y,z,dis[100005];
bool vis[100005];
struct stu{
	int to,num;
};
vector<stu> v[100005];
struct node{
	int p,d;
	bool operator<(const node &x) const{
		return x.d<d;
	}
};
priority_queue<node> q;
signed main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		v[x].push_back((stu){y,z});
	}
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	q.push((node){s,0});
	while(!q.empty()){
		node f=q.top();
		q.pop();
		if(vis[f.p]) continue;
		vis[f.p]=1;
		for(int i=0;i<v[f.p].size();i++){
			int xx=v[f.p][i].to;
			if(dis[xx]>dis[f.p]+v[f.p][i].num){
				dis[xx]=dis[f.p]+v[f.p][i].num;
				if(!vis[xx]){
					q.push((node){xx,dis[xx]});
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}