#include <bits/stdc++.h>
using namespace std;
#define maxn 100000+10
int n,m;
//顶点的数量 边的数量

struct node {
	int v,w;
	//顶点和边的权值
};
bool operator < (const node& a,const node& b) {
	return a.w>b.w;
	//从小到大排列边的权值
}
vector <node> g[maxn];
//记录从原点到其它剩余节点的最短路
int f[maxn];
bool vis[maxn];
priority_queue<node> q;
void dijkstra(int s){
	for(int i=1;i<=n;i++){
		f[i]=1<<30;
	}
	f[s]=0;//赋予起始点
	q.push( (node){s,0} );
	
	while(q.size()!=0){
		node t=q.top();
		q.pop();
		if(vis[t.v]) continue;
		else vis[t.v]=1;
		for(int i=0;i<g[t.v].size();i++){
			node to=g[t.v][i];
			if(f[to.v]>f[t.v]+to.w){
				f[to.v]=f[t.v]+to.w;
				q.push((node){t.v,f[t.v]});
			}
		}
	}
	
}
int main(){
	int start;
	scanf("%d%d%d",&n,&m,&start);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		g[x].push_back( (node){y,z} );
	}
	dijkstra(start);
	for(int i=1;i<=n;i++){
		printf("%d ",f[i]);
	}
	return 0;
}