代码：

#include<bits/stdc++.h>
#define MAXN 500010
using namespace std;
const int inf=2147483647;
int n,m,s,cnt;
int dis[MAXN],h[MAXN],to[MAXN],val[MAXN],nxt[MAXN];
bool vis[MAXN];
void add(int a,int b,int c){
	to[++cnt]=b;
	val[cnt]=c;
	nxt[cnt]=h[a];
	h[a]=cnt;
	return;
}
int Dijkstra(){
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
	dis[s]=0;
	dis[0]=inf;
	while(1){
		int u=0;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[u]>dis[i]){
				u=i;
			}
			if(u==0) break;
			vis[u]=1;
			for(int i=h[u];i;i=nxt[i]){
				if(dis[to[i]]>(long long)dis[u]+val[i]){
					dis[to[i]]=dis[u]+val[i];
				}
			}
		}
	}
}
int main(){
	scanf("%d %d %d",&n,&m,&s);
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	Dijkstra();
	for(int i=1;i<=n;i++){
		printf("%d ",dis[i]);
	}
	return 0;
}