#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
struct Edge{
	int to,w;
};

const int N = 2e5+ 10;
int n,m,st,x,y,w,dist[N],vis[N];
vector <Edge> g[N];
priority_queue < pair<int,int> > p;

void dijkstra(int st,int end);

int main(){
	//freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>m>>st;
	for(int i=0;i<m;i++){
		cin>>x>>y>>w;
		g[x].push_back(Edge{y,w});
	}
	dijkstra(st,n);
	for(int i=1;i<=n;i++){
		if(dist[i] == 0x3f3f3f3f) cout<<(1<<31)-1<<" ";
		else cout<<dist[i]<<" ";
	}
	cout<<endl;
	return 0;
}

void dijkstra(int st,int end){
	memset(dist,0x3f,sizeof dist);
	memset(vis,0,sizeof vis);
	dist[st]=0;
	p.push( make_pair(0,st) );
	while(!p.empty()){
		int a=p.top().second;
		p.pop();
		if(vis[a])continue;
		vis[a]=1;
		int cnt=g[a].size();
		for(int i=0;i<cnt;i++){
			int yy=g[a][i].to,ww=g[a][i].w;
			if(dist[yy] > dist[a]+ww){
				dist[yy]=dist[a]+ww;
				p.push( make_pair(-dist[yy],yy) );
			}
		}
	}
}

求看