RT:

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+5;
struct node{
	int id,val;
};
vector<node> G[maxn];
int n,m,s,dis[maxn];
void BFS(int s){
	queue<node> q;
	memset(dis,inf,sizeof(dis));
	q.push(node({s,0}));
	while(!q.empty()){
		int x=q.front().id,y=q.front().val;
		q.pop();
		if(dis[x]<=y)
			continue;
		dis[x]=y;
		for(int i=0,l=G[x].size();i<l;i++)
			if(G[x][i].val+dis[x]<dis[G[x][i].id])
				q.push(node({G[x][i].id,G[x][i].val+dis[x]}));
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	while(m--){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		G[x].push_back(node({y,z}));
	}
	BFS(s);
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
	return 0;
}