#include<bits/stdc++.h>
using namespace std;
struct node{
	int to,w;
	bool operator<(const node&a)const{
		w>a.w;
	}
};
priority_queue<node>q;
vector<node>a[10005];
int dist[10005],n,m,s;
int flag[10005];
int main(){
	memset(dist,0x7f,sizeof dist);
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[x].push_back(node{y,z});
	}
	dist[s]=0;
	q.push(node{s,0});
	for(int i=1;i<=n;i++){
		q.push(node{i,2147483647});
	}
	for(int i=1;i<=n;i++){
		qushu:;
		int tot=q.top().to;
		q.pop();
		if(flag[tot])goto qushu;
		flag[tot]=1;
		for(int j=0;j<a[tot].size();j++){
			if(dist[a[tot][j].to]>dist[tot]+a[tot][j].w){
				dist[a[tot][j].to]=dist[tot]+a[tot][j].w;
			}
			q.push(node{a[tot][j].to,dist[a[tot][j].to]});
		}
	}
	for(int i=1;i<=n;i++)cout<<dist[i]<<' ';
	return 0;
}

望dalao帮调（哭辽，整了一夜代码