#include<bits/stdc++.h>
	using namespace std;
	struct edge{
	    int v,w;
	};
	int n,m,s;
	vector<edge> g[100100];
	int dis[100100];
	struct node{
	    int num,dis;
	};
	bool operator<(node a,node b){
	    return a.dis>b.dis;
	}
	priority_queue<node> q;
	int vis[100100];
	void dijkstra(){
	    for(int i=1;i<=n;i++) dis[i]=INT_MAX;
	    dis[s]=0;
	    q.push({s,0});
	    while(!q.empty()){
	        node tmp=q.top();
	        int u=tmp.num;
	        if(vis[u]) continue;
	        vis[u]=1;
	        for(int i=0;i<g[u].size();i++){
	            int v=g[u][i].v,w=g[u][i].w;
	            if(dis[v]>dis[u]+w){
	                dis[v]=dis[u]+w;
	                q.push({v,dis[v]});
	            }
	        }
	    }
	}
	int main(){
		cin>>n>>m>>s;
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			g[u].push_back({v,w});
		}
		dijkstra();
		for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
		return 0;
	}