2，3，6ac，其余wa

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

struct tu{
	int now=0;
	int next=0;
	int towhat=0;
	int lenth=0;
}a[200001];

int rc[100001];
int ans[100001];
bool chk[100001];
int n,m,s;

struct cmp{
	bool operator()(int a1,int b1){
		return ans[a1]>ans[b1];
	}
};


void dij(){
	priority_queue <int,vector<int>,cmp> qp;
	int tmp1=s;
	do{
		tmp1=rc[tmp1];
		while(a[tmp1].now!=0){
			if(a[tmp1].lenth+ans[a[tmp1].now]<ans[a[tmp1].towhat]) ans[a[tmp1].towhat]=a[tmp1].lenth+ans[a[tmp1].now];
			qp.push(a[tmp1].towhat);
			tmp1=a[tmp1].next;
		}	
		
		tmp1=qp.top();
		while(chk[tmp1]==true&&qp.empty()==false){
			qp.pop();
			tmp1=qp.top();
		}
		if(qp.empty()==true) break;
		chk[tmp1]=true;
		//cout<<qp.top()<<'\n';
		qp.pop();
	}while(qp.empty()==false);
	return;
}

int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
	int i;
	memset(ans,9999999,sizeof(ans));
	memset(chk,false,sizeof(chk));
	cin>>n>>m>>s;
	//cout<<'\n';
	ans[s]=0;
	chk[s]=true;
	for(i=1;i<=m;i++){
		cin>>a[i].now>>a[i].towhat>>a[i].lenth;
		a[i].next=rc[a[i].now];
		rc[a[i].now]=i;
	}
	
	dij();
	
	for(i=1;i<=n;i++){
		cout<<ans[i]<<' ';
		}
	
}