//Bellman_Ford
//只过了一半(っ °Д °;)っ

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

const int maxn = 10005;
const int maxm = 500005;

int n, m, s;
int dis[maxn];

struct edge{
	int u, v, w;
}e[maxm];

void bellman_ford(){
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int u = e[j].u; int v = e[j].v;
			int w = e[j].w;
			if(dis[v] > dis[u]+w)
				dis[v] = dis[u]+w;
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1; i<=m; i++){
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	bellman_ford();
	for(int i=1; i<=n; i++)
	 	cout<<dis[i]<<" ";
	return 0;
} 

//SPFA
//介个......蛙声一片━((*′д｀)爻(′д｀*))━!!!!

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

const int maxn = 10005;
const int maxm = 500005;

int n, m, s;
int dis[maxn], cnt[maxn], vis[maxn];
int x;

struct edge{
	int v, w;
}e[maxm];

queue<int> q;

void spfa(int n, int s){
	memset(dis, 63, sizeof(dis));
	dis[s] = 0;
	vis[s] = 1;
	q.push(s);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		int v = e[u].v;
		int w = e[u].w;
		if(dis[v] > dis[u]+w){
			dis[v] = dis[u]+w;
			cnt[v] = cnt[u] + 1;
//			if(cnt[v] >= n) return false;
			if(!vis[v]){
				q.push(v);
				vis[v] = 1;
			}
		}
	}
//	return false;
}

int main(){
	cin>>n>>m>>s;
	for(int i=1; i<=m; i++){
		cin>>x>>e[i].v>>e[i].w;
		q.push(x);
	}
	spfa(n, s);
	for(int i=1; i<=n; i++)
		cout<<dis[i]<<" ";
	return 0;
}