3371 90分，第三个测试点

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,s,dis[100010];
bool flag[100010];
struct node{
	int to,w;
};
vector<node>a[100010];
queue<int>q;
int main(){
	cin>>n>>m>>s;
	int i;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		a[x].push_back({y,z});
	}
	for(i=1;i<=n;i++)dis[i]=INT_MAX/2;
	q.push(s);
	dis[s]=0;
	flag[s]=1;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		flag[t]=0;
		for(i=0;i<a[t].size();i++){
			int e=a[t][i].to;
			if(dis[e]>dis[t]+a[t][i].w){
				dis[e]=dis[t]+a[t][i].w;
				if(flag[e]==0){
					flag[e]=1;
					q.push(e);
				}
			}
		}
	}
	for(i=1;i<=n;i++)cout<<dis[i]<<' ';
	return 0;
}