#include<bits/stdc++.h>
using namespace std;

int head[100004];
struct edge{ //链式前向星存图   相当于 存储和这个点相连的所有点 
  int to,next,w;  //终点 下一条边 权值 
}a[1000004];
int cnt=0;
long long dis[10004];
bool vis[10004];
int n,m,s;
long long M=2147483647;
    
void add(int u,int v,int w){
    cnt++;
    a[cnt].to=v;
    a[cnt].w=w;
    a[cnt].next=head[u];
    head[u]=cnt;
}

struct node{
    int w,now;
    inline bool operator<(const node &x)const{
        return w>x.w;
    }
};

int main(){
	cin>>n>>m>>s;
	
	for(int i=1;i<=n;i++){
		dis[i]=M;
	}	
	dis[s]=0;
	int x,y,v;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>v;
		add(x,y,v);
	}
	
	priority_queue<node>q;  
	q.push((node){0,s});
	
	while(!q.empty()){
		node pos=q.top();
		q.pop();
		int k=pos.now,minn=M;
		if(k==0){
			cout<<2147483647;
			return 0;
		}
		vis[k]=1;
		for(int j=head[k];j!=0;j=a[j].next){
			if(dis[k]+a[j].w<dis[a[j].to]){
				dis[a[j].to]=dis[k]+a[j].w;
				q.push((node){dis[a[j].to],a[j].to});
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

记录