#include<iostream>
#include<vector>
#include<queue>
using namespace std;
struct node{
	int v,w;
};
int n,m,s;
vector<node>edge[100001];
struct node1{
	int idx,dis,vis;
	bool operator<(const node1 &xd) const{
		return dis>xd.dis;
	}
}vtxs[100001];
void dij(int s){
	priority_queue<node1>q;
	q.push({s,0,0});
	vtxs[s].dis=0;
	while(!q.empty()){
		int u=q.top().idx;
		q.pop();
		if(vtxs[u].vis) continue;
		vtxs[u].vis=1;
		for(node x:edge[u]){
			int v=x.v;
			int w=x.w;
			if(!vtxs[v].vis&&vtxs[v].dis>vtxs[u].dis+w){
				vtxs[v].dis=vtxs[u].dis+w;
				q.push({v,vtxs[v].dis});
			}
		} 
	}
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edge[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++){
		vtxs[i].dis=0x3f3f3f3f;
	}
	dij(s);
	for(int i=1;i<=n;i++){
		cout<<vtxs[i].dis<<" ";
	}
	return 0;
}