#include<bits/stdc++.h>
using namespace std;
int n,m,s,dis[100005],vis[100005];
struct node {
	int v,w;
};
struct edge {
	int v,dis;
	bool operator<(const edge&y)const{
		return dis>y.dis;
	}
};
vector<node>e[100005];
void dijkstra(int s){
	for(int i=1;i<=n;i++){
		if(i!=s)dis[i]=1e9;
	}
	priority_queue<edge>q;
	q.push({s,0});
	while(!q.empty()){
		int u=q.top().v;
		q.pop();
		if(vis[u]==1)continue;
		vis[u]=1;
		for(int i=0;i<e[u].size();i++){
			int v=e[u][i].v;
			int w=e[u][i].w;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main(){
	int x,y,niba;
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>niba;
		e[x].push_back({y,niba});
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
	return 0;
}