#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int> >f[100001];//邻接表存图
int dis[100001];//最短路长度
bool d[100001];//是否标记过最短
int n,m,s,a,b,c;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;//堆优化 
int main(){
	memset(dis,INT_MAX,sizeof(dis));
	memset(d,1,sizeof(d));
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		f[a].push_back(make_pair(b,c));
	}//输入
	q.push(make_pair(s,0));
	dis[s]=0;
	while(!q.empty()){
		int x=q.top().first;
		d[x]=0;
		for(int i=0;i<f[x].size();i++){
			dis[f[x][i].first]=min(dis[f[x][i].first],dis[x]+f[x][i].second);
			if(d[f[x][i].first]==1){
				q.push(make_pair(f[x][i].first,f[x][i].second));
			}
		}
	}
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}