#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

int dis[100005],p[100005],head[100005],n;
bool vis[100005];
struct edge{
	int v,w,next;
}e[200005];
struct node{
	int num,w;
	inline bool operator<(const node &x)const{return w<x.w;}
};

void dijkstra(int s){
	priority_queue<node> q;
	dis[s]=0;
	q.push(node{s,0});
	while(!q.empty()){
		node v=q.top();
		q.pop();
		if(vis[v.num])continue;
		vis[v.num]=1;
		for(int i=head[v.num];i;i=e[i].next){
			if(dis[e[i].v]>dis[v.num]+e[i].w){
				dis[e[i].v]=dis[v.num]+e[i].w;
				if(!vis[e[i].v])q.push(node{e[i].v,dis[e[i].v]});
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m,s;
	cin >> n >> m >> s;
	for(int i=1;i<=n;i++)dis[i]=0x7fffffff;
	for(int i=1;i<=m;i++){
		int u;
		cin >> u >> e[i].v >> e[i].w;
		e[i].next=head[u];
		head[u]=i;
	}
	dijkstra(s);
	for(int i=1;i<=n;i++)cout << dis[i] << " ";
	return 0;
}

自己瞎编了几个样例也能过，但只有#5 AC