#include<bits/stdc++.h>
#define ll unsigned long long
const ll N = 1000005;
const ll INF = 0x3f3f3f3f;
using namespace std;
struct node{
	int pos, dis;
	bool friend operator < (node A, node B){
		return A.dis < B.dis;
	}
};
struct edge{
	int to, nxt, w;
}a[N];
int n, m, s, u, v, z, head[N], inde, dis[N];
bool vis[N];
void add(int x, int y, int w) {
	a[++inde].to = y;
	a[inde].nxt = head[x];
	a[inde].w = w;
	head[x] = inde;
}
priority_queue<node> Q;
void dijistra() {
	for(int  i = 1; i <= n; i++) dis[i] = INF;
	dis[s] = 0;
	Q.push((node{s, 0}));
	while(!Q.empty()){
		node f = Q.top(); 
		Q.pop();
		int x = f.pos, d = f.dis;
		if(vis[x]) continue;
		vis[x] = 1;
		for(int i = head[x]; i; i = a[i].nxt) {
			int y = a[i].to;
			if(dis[y] > dis[x] + a[i].w) {
				dis[y] = dis[x] + a[i].w;
				if(!vis[y]) Q.push(node{y, dis[y]}); 
			}
		}
		
	}
}
int main(){
	cin >> n >> m >> s;
	for(int i = 1; i <= m ; i ++) {
		cin >> u >> v >> z;
		add(u, v, z);
	}
	dijistra();
	for(int i = 1; i <= n; i++){
		cout<< dis[i] <<" ";
	}
 	return 0;
}