#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 600010;

struct edge{//用于存图; 
	int to;
	int dis;
	edge(int a,int b){
		to = a;
		dis = b;
	}
};
struct node{//用于建堆; 
	int x;
	int len;
	node(int a,int b){
		x = a;
		len = b;
	}
};

bool operator < (const node &a,const node &b){
	return a.len > b.len;//建立小根堆
	//return a.len < b.len建立大根堆; 
} 

int n,m,s;
int dis[N];
vector<edge> g[N];
int v[N];
priority_queue<node> que;//堆;

void Dijkstra(int s){
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0;
	que.push(node(s,dis[s]));
	while(!que.empty()){
		int x = que.top().x;
		que.pop();
		if(v[x] == 0){
			v[x] = 1;
			for(int i = 0 ; i < g[x].size() ; i++){
				int y = g[x][i].to;
				int w = g[x][i].dis;
				if(dis[y] > dis[x] + w){
					dis[y] = dis[x] + w;
					que.push(node(y,dis[y]));
				}
			}
		}
	}
} 
signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	cin >> n >> m >> s;
	for(int i = 1 ; i <= m ; i++){
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back(edge(v,w));
	}
	Dijkstra(s);
	for(int i = 1 ; i <= n ; i++){
		cout << dis[i] << " ";
	}
	cout << endl;
	return 0; 
}