#include <bits/stdc++.h>
using namespace std;
const int M = 200020;
long long INF = 1e9;//0x3f   0x7fffffff  2147483647
int n,m,aim,cnt;
long long d[M];
bool vis[M];
struct node{
	int to;
	long long vlu;
	friend bool operator < (const node &x,const node &y) {return x.vlu > y.vlu;} 
};
priority_queue<node> G;
vector<node> adj[M];
inline void read(int& qwq){
	int awa = 0,w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') w = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		awa = awa * 10 + ch - '0';
		ch = getchar();
	}
	qwq = awa * w;
}
void insert_edge(int u,int v,long long w){
	node pll;
	pll.to = v;
	pll.vlu = w;
	adj[u].push_back(pll);
}
void get(){
	cin>>n>>m>>aim;
	int u,v;
	long long w;
	for(int i=1;i<=m;i++){
		read(u),read(v);
		scanf("%lld",&w);
		insert_edge(u,v,w);
		//insert_edge(v,u,w);
	}
	for(int i=1;i<=n;i++) d[i] = INF;
}
void put(int u){
	int v = 0;long long w = 0;node pll;
	cnt++;
	vis[u] = 1;
	for(int i=0;i<adj[u].size();++i){
		v = adj[u][i].to,w = adj[u][i].vlu;
		if(!vis[v] && d[v] > d[u] + w){
			d[v] = d[u] + w;
			pll.to = v,pll.vlu = d[v];
			G.push(pll);
		}
	}
}
int pop(){
	int v = G.top().to,pop_temp = 0;
	while(vis[v] && !G.empty()) G.pop();
	if(!G.empty()){
		pop_temp = G.top().to;
		G.pop();
	}
	return pop_temp;
}
void kri(int s){
	int v,w;
	d[s] = 0;
	put(s);
	while(cnt <= n && !G.empty()){
		v = pop();
		put(v);
	}
}
int main(){
//	freopen("P4779_1.in","r",stdin);
	get();
	kri(aim);
	for(int i=1;i<=n;i++) printf("%lld ",d[i]);
	return 0;
}