#include<bits/stdc++.h>
using namespace std;
queue<int> v;
struct node{
	int dian,len;
};
vector<node> x[10005];
int vis[10005];
int n,m,s;
void bfs(){
	while(!v.empty()){
		int f=v.front();
		v.pop();
		for(int k=1;k<=x[f].size();k++){
			if(vis[x[f][k].dian]>vis[f]+x[f][k].len){
				vis[x[f][k].dian]=vis[f]+x[f][k].len;
				v.push(x[f][k].dian);
			}else{
				continue;
			}
		}
	}
	return;
}
int main(){	
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,f;
		cin>>u>>v>>f;
		x[u].push_back(node{v,f});
	}
	v.push(s);
	bfs();
	for(int i=1;i<=n;i++){
		cout<<vis[i]<<" ";
	}
	return 0;
}