code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,d[1000001],lon;
bool flag[1000001];
struct node{
	int l,num;
};
struct edge{
	int num,len;
};
void swp(edge x,edge y){
//	edge zzz=x;
//	y=x;
//	x=zzz;
	swap(x,y);
}
edge dui[1000001];
vector<node>vec[1000001];
void pop(int x){
	dui[x].num=dui[lon].num;
	dui[x].len=dui[lon].len;
	dui[lon].num=0;
	dui[lon].len=0;
	lon--;
	int fa=x,so=x*2;
	while(so<=lon){
		if(so+1<=lon&&dui[so].len>dui[so+1].len)so++;
		if(dui[fa].len>dui[so].len){
//			swap(dui[fa],dui[so]);
			int a=dui[fa].num,b=dui[fa].len,c=dui[so].num,da=dui[so].len;
			dui[fa].num=c;
			dui[fa].len=da;
			dui[so].num=a;
			dui[so].len=b;
//			swap(dui[fa].num,dui[so].num);
//			swap(dui[fa].len,dui[so].len);
		}		
		else break;
//		cout<<so<<endl;
		fa=so;
		so*=2;
	}
}
void push_up(int x,int y){
	lon++;
	dui[lon].num=x;
	dui[lon].len=y;
	int fa=lon/2,so=lon;
	while(fa){
//		cout<<dui[fa].len<<" "<<dui[so].len<<endl;
		if(dui[fa].len>dui[so].len){
//			swap(dui[fa],dui[so]);
			int a=dui[fa].num,b=dui[fa].len,c=dui[so].num,da=dui[so].len;
			dui[fa].num=c;
			dui[fa].len=da;
			dui[so].num=a;
			dui[so].len=b;
//			swap(dui[fa].num,dui[so].num);
//			swap(dui[fa].len,dui[so].len);
		}
		else break;
		so=fa;
		fa/=2;
	}
}
signed main(){
	cin>>n>>m>>s;
	for(int x,y,sum,i=1;i<=m;i++){
		cin>>x>>y>>sum;
		vec[x].push_back({y,sum});
	} 
	for(int i=1;i<=n;i++)d[i]=2147483647;
	d[s]=0;
	push_up(s,0);
	for(int i=1;i<=n;i++){
		int hed=dui[1].num;
		if(flag[hed])continue;
		flag[hed]=1;
//		cout<<dui[1].num<<" "<<dui[1].len<<" "<<i<<endl;
		pop(1);		
		for(int i=0;i<vec[hed].size();i++){
			if(vec[hed][i].num+d[hed]<d[vec[hed][i].l]){
				d[vec[hed][i].l]=d[hed]+vec[hed][i].num;
//				cout<<d[hed]<<endl;
				push_up(vec[hed][i].l,d[vec[hed][i].l]);
			}
		}		
	}
	for(int i=1;i<=n;i++)
		cout<<d[i]<<" ";
	return 0;
} 

record