#include <bits/stdc++.h>

using namespace std;
int to[500100];
int val[500100];
int net[500100];
int h[500100];
int dis[500100];
int vis[500100];
int cnt;
int n,m,s;
int _memset() {
	for(int i=1; i<=n; i++) {
		dis[i]=2147483647;
	}
	return 0;
}
int add(int f,int t,int v) {
	to[++cnt]=t;
	val[cnt]=v;
	net[cnt]=h[f];
	h[f]=cnt;
	return 0;
}
int dijkstra() {
	_memset();
	dis[0]=2147483647;
	dis[s]=0;
	while(true) {
		int ne=0;
		for(int i=1; i<=n; i++) {
			if(vis[i]==0 and dis[i]<dis[ne]) {
				ne=i;
			}
		}
		if(ne==0) {
			break;
		}
		vis[ne]=1;
		for(int i=h[ne]; i; i=net[i]) {
			if(dis[to[i]]>(long long)(dis[ne]+val[i])) {
				dis[to[i]]=dis[ne]+val[i];
			}
		}
	}
}
int main() {
	cin>>n>>m>>s;
	for(int i=1; i<=m; i++) {
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,c);
	}
	dijkstra();
	for(int i=1; i<=n; i++) {
		cout<<dis[i]<<" ";
	}
	return 0;
}