#include<bits/stdc++.h>
//#include<stdlib>
#define int long long 
using namespace std;

int n,m,s;
int uu,vv,ww;
vector<pair<int,int> > g[500005];
priority_queue<pair<int,int > > q;
int dis[500005],vis[500005];
int u;

inline int read(){
	int s=0,w=1;
	char ch=getchar();
	while(ch>'9'||ch<'0')w=(ch=='-'?-1:1),ch=getchar();
	while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}

inline void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
//	cout<<x<<endl;
	putchar((x%10)+'0');
}

inline void dij(int s) {
//	memset(dis,127,sizeof dis);
	for(int i=0;i<=n+1;i++)dis[i]=1e20;
//	vis[s]=1,
	dis[s]=0;
	q.push({0,s});
	while(!q.empty()) {
		u=q.top().second;
		q.pop();
		if(vis[u])continue;
		vis[u]=1;
		for(auto v:g[u]) 
			if(dis[v.first]>dis[u]+v.second) {
				dis[v.first]=dis[u]+v.second;
				if(!vis[v.first])q.push({-v.second,v.first});
			}
	}
}

signed main() {
//	scanf("%d%d%d",&n,&m,&s);
	n=read(),m=read(),s=read();
//	cout<<n<<m<<s;
	for(register int i=1; i<=m; i++) {
//		scanf("%d%d%d",&uu,&vv,&ww);
		uu=read(),vv=read(),ww=read();
		g[uu].push_back({vv,ww});
	}
	dij(s);
	for(register int i=1; i<=n; i++)write(dis[i]),putchar(' ');
}

rt 52pts 刚学不会调，求助

https://www.luogu.com.cn/record/list?pid=P4779&user=1095058