源代码：

#include<bits/stdc++.h>
using namespace std;
struct pir{
	short x,y;
}hp[500500];
int hs;
int h[100020],v[100020],w[100020],ne[100020],tot;
int mindis[100020];
int n,m,book[100020],k;
void add(int a,int b,int c){
	v[tot]=b,w[tot]=c,ne[tot]=h[a];
	h[a]=tot++;
}
void siftdown(int i)
{
	if(i==0)return;
	int t=i;
	while(2*i<=hs)
	{
		if(hp[2*i].x<hp[t].x)
			t=2*i;
		if(2*i+1<=hs&&hp[2*i+1].x<hp[t].x)
			t=2*i+1;
		if(i!=t)
			swap(hp[i],hp[t]);
		else
			return;
		i=t;
	}
	return ;
}

void siftup(int i)
{
	while(i>1)
	{
		if(hp[i].x<hp[i/2].x)
			swap(hp[i],hp[i/2]);
		else
			return;
		i/=2;
	}
	
	return;
}
int main(){
// 	freopen("dijkstra.in","r",stdin);
	for(int i=1;i<=100010;i++){
		mindis[i]=0x7fffffff;
	}
	memset(h,-1,sizeof h);
	
	
	int a,b,c,t;
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		cin>>a>>b>>c;
		add(a,b,c);
	}
	
//	for(int i=h[1];~i;i=ne[i]){
//		mindis[v[i]]=w[i];
//	}
	hp[1].x=0;
	hp[1].y=k;
	hs++;	
	mindis[k]=0;
	while(hs){
		t=hp[1].y;
		hp[1]=hp[hs--];
		siftdown(1);
		
		if(book[t])continue;
		book[t]=1;

		for(int j=h[t];~j;j=ne[j]){
			b=v[j];
			if(book[b]==0&&mindis[b]>mindis[t]+w[j]){
				mindis[b]=mindis[t]+w[j];
			}
			hs++;
			hp[hs].x=mindis[b];
			hp[hs].y=b;
			siftup(hs);  
		}
	} 
	for(int i=1;i<=n;i++){
		cout<<mindis[i]<<' ';
	}
	return 0;
}