#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
#define MAXN 500001
int dis[MAXN];
int u[MAXN],v[MAXN],w[MAXN];
int first[MAXN],next[MAXN];
int sign[MAXN];
int n,m,N=0;
int src,ed;
struct qu{
	int v;
	int dis;
};
struct qu que[MAXN];
struct qu tmp;
int read(){
	int p=0,f=1;	char	c=getchar();
	while (c<48||c>57)	{if (c=='-')	f=-1;	c=getchar();}
	while (c>=48&&c<=57)	p=(p<<1)+(p<<3)+c-48,c=getchar();
	return p*f;
}
void init()
{
    n=read();
    m=read();
    src=read();
    memset(first,-1,sizeof(first));
    int i;
    for(i=1;i<=m;i++){
    	u[i]=read();
    	v[i]=read();
    	w[i]=read();
        next[i]=first[u[i]];
        first[u[i]]=i;
    }
    for(i=1;i<=n;i++) dis[i]= (i==src? 0:1e10);
}
void wei_min(int i){
	int p;
	for(;(p=2*i)<=N;i=p){
		if(p+1<=N&&que[p].dis>que[p+1].dis){
			p++;
		}
		if(que[p].dis<que[i].dis){
			tmp=que[p];
			que[p]=que[i];
			que[i]=tmp;
		}
		else{
			break;
		}
	}
}
void pop() {
	que[1]=que[N--];
	wei_min(1);
}
void push(int dis,int v){
	int i,j;
	++N;
	que[N].v=v;
	que[N].dis=dis;
	for(i=N/2,j=N;i>=1&&que[i].dis>v;i/=2,j/=2){
		tmp=que[i];
		que[i]=que[j];
		que[j]=tmp;
	}
}
void dijkstra()
{
    push(0,src);
    int x,di,e;
    while(N!=0){
		x = que[1].v;
		di=que[1].dis;
        pop(); 
        if(di!=dis[x]) continue;  
        for(e=first[x];e!=-1;e=next[e]){ 
            if(dis[v[e]]>dis[x]+w[e]){
                 dis[v[e]]=dis[x]+w[e];
                 push(dis[v[e]],v[e]);
            }
        }
    }
 
}
int main()
{
    init();
    dijkstra();
    int i;
    for(i=1;i<=n;i++) printf("%d ",dis[i]);
}

全部手写的，不知道哪有问题，是不是队列用了struct而不是C++的pair就错了呀？