#include<bits/stdc++.h>
using namespace std;
struct e1{
	int to,nxt,w;
}e[6000600];
long long n,m,s; 
long long dis[6000020],vis[6000050],h[6000500],cnt=0;
void add(int x,int y,int z){
	cnt++;
	e[cnt].nxt=h[x]; 
	e[cnt].to=y;	
	e[cnt].w=z;
	h[x]=cnt;

}
void spfa(int x){
	for(int i=1;i<=n;i++){
		dis[i]=1e5; 
		vis[i]=0;
	}
	dis[s]=0; //起点到起点为0；
	vis[s]=1;
	//vis表示s还在队列中 
	queue<int> p;
	p.push(s); 
	while(!p.empty()){
		int x=p.front();
		vis[x]=0;
		p.pop();
		for(int i=h[x];i;i=e[i].nxt){
			
			if(dis[e[i].to]>dis[x]+e[i].w){
				dis[e[i].to]=dis[x]+e[i].w;
				if(!vis[e[i].to]){
					vis[e[i].to]=1;
					p.push(e[i].to);
				}
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	spfa(s);
	for(int i=1;i<=n;i++){
		printf("%lld ",dis[i]);
	}
	return 0;
}

样例过了，但一分不得