#include<bits/stdc++.h>
using namespace std;
const int N = 1010;//点数最大值 
const int M = 1e4 + 10;//边数最大值 
const int inf = 0x7fffffff;//极大值 
typedef long long ll;
queue<ll>q;
ll dis[N],vis[N],head[N],to[N],nex[N],val[M];
ll cnt,n,m,s;
void add(int u,int v,int w){
	to[++cnt] = v;
	val[cnt] = w;
	nex[cnt] = head[u];
	head[u] = cnt;
}//链式前向星加边 
void spfa(){
	memset(dis,inf,sizeof dis);
	q.push(s);
	dis[s] = 0;
	vis[s] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i=head[u];i!=0;i=nex[i]){
			int v = to[i];
			if(dis[v] > dis[u] + val[i]){
				dis[v] = dis[u] + val[i];
				if(!vis[v]){
					q.push(v);
					vis[v] = 1;
				}
			}
		}
	}
}//跑spfa 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>s;
	int u,v,w;
	while(m--){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	spfa();
	for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
	return 0;
}