记录

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct edge{
	int v,value,next=0;
}d[500005];
int n,m,s,u,v,w,tot=0,head[10005],ans[10005];
bool vis[10005]={false};
priority_queue<pair<int,int> >q;
void add(int u,int v,int w){
	d[++tot].v=v;
	d[tot].value=w;
	d[tot].next=head[u];
	head[u]=tot;
}
void dijkstra(){
	memset(ans,0x3f,sizeof(ans));
	memset(vis,0,sizeof(vis));
	ans[s]=0;
	q.push(make_pair(0,s));
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x])continue;
		vis[x]=1;
		for(int i=head[x];i;i=d[i].next){
			int y=d[i].v,z=d[i].value;
			if(ans[y]>=ans[x]+z){
				ans[y]=ans[x]+z;
				q.push(make_pair(-ans[y],y));
			}
		}
	}
}
signed main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
	}
	dijkstra();
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
}