#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<map>
#include<set>
using namespace std;

struct edge{
	int to,w,next;
}edges[1000005];

int  n,m,s,cnt=0;
int vis[10005],dis[10005],head[100005];

void eddEdge(int u,int v,int w){
	edges[++cnt].to=v;
	edges[cnt].w=w;
	edges[cnt].next=head[u];
	head[u]=cnt;
}

void dij(int s){
	priority_queue <int,vector<int>,greater<int>> que;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	que.push(s);
	while(!que.empty()){
		int st=que.top();
		que.pop();
		if(vis[st]){
			continue;
		}
		vis[st]=1;
		for(int i=head[st];i!=0;i=edges[i].next){
			int to=edges[i].to;
			dis[to]=min(dis[to],dis[st]+edges[i].w);
			que.push(to);
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		eddEdge(u,v,w);
	}
	dij(s);
	for(int i=1;i<=n;i++){
		int cc=pow(2,31)-1;
		if(dis[i]==0x3f3f3f3f){
			cout<<cc<<" ";
		}else{
			cout<<dis[i]<<" "; 
		}
	}
	return 0;
}

测评