#include<bits/stdc++.h>
using namespace std;
#define N 100001
struct edge{int v,w;};
vector<edge> e[N];
int d[N],vis[N],n,m;
priority_queue<pair<int,int> > q;
void dijkstra(int s){
	for(int i=0;i<=n;i++)d[i]=8438584;
	d[s]=0;q.push({0,s});
	while(q.size()){
		auto t=q.top();q.pop();
		int u=t.second;
		if(vis[u])continue;
		vis[u]=1;
		for(auto ed:e[u]){
			int v=ed.v,w=ed.w;
			if(d[v]>d[u]+w){
				d[v]=d[u]+w;
				q.push({-d[v],v});
			}
		}
	}
}
int main(){
    int s;
	cin>>n>>m>>s;
    int a,b,c;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
        e[a].push_back(edge{b,c});
    }
	    dijkstra(s);
    for(int i=1;i<=n;i++){
        cout<<d[i]<<" ";
    }
	return 0;
}