#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> pii;
const int N = 10001,M = 500001,inf = 0x7f7f7f7f;
int n,m,s,cnt,head[N],dis[N],vis[N];
struct edge {
    int u,v,w,next;
}e[M];
priority_queue<pii,vector<pii>,greater<pii>> q;

void add(int u,int v,int w){
	e[++cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
    e[cnt].next = head[u];
    head[u] = cnt;
}

void dijkstra(){
	q.push({0,s});
	while(!q.empty()){
		pii src = q.top();
		q.pop();
		int u = src.second;
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i=head[u]; i!=0; i=e[i].next){
			int v = e[i].v;
			if(dis[v] > dis[u] + e[i].w){
				dis[v] = dis[u] + e[i].w;
				q.push({dis[v],v});
			}
		}
	}
}

int main(){
	cin >> n >> m >> s;
	memset(dis,inf,sizeof(dis));
	dis[s] = 0;
	for(int i=1; i<=m; i++){
	    int u,v,w;
	    cin >> u >> v >> w;
	    add(u,v,w);
	}
	dijkstra();
	for(int i=1; i<=n; i++){
	    cout << dis[i] << " ";
	}
    return 0;
}