#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
vector<PII>pos[10010];
int ys,dis[10100],vis[10100],n,m,xs;
queue<int>djstl;
int bfs(int x){
    vis[x]=1;
	djstl.push(x);
	while(!djstl.empty()){
		int go=djstl.back();
		djstl.pop();
		for(auto i:pos[go]){
			int to=i.first,sp=i.second;
			if(dis[to]>dis[go]+sp){
				dis[to]=dis[go]+sp;
				djstl.push(to);
			}
		}
	}
}
int main(){
	cin>>n>>m>>xs;
	for(int i=0;i<m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		pos[x].push_back({y,z});
	}memset(dis,INT_MAX,sizeof dis);
	dis[xs]=0;
	bfs(xs);
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<' ';
	}
}