RT，RDM

#include<bits/stdc++.h>
using namespace std;
const int maxn=99999999;
int n,m,s,f[10001][10001],v[10001],c[10001]; 
int main(){
	scanf("%d %d %d",&n,&m,&s);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			f[i][j]=maxn;
		}
	}
	for (int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		f[u][v]=w;
	}
	
	for (int i=1;i<=n;i++) c[i]=f[s][i]; 
	v[s]=1;c[s]=0;
	for (int i=1;i<=n-1;i++){
		int minn=maxn,jl=0;
		for (int j=1;j<=n;j++)
			if ((!v[j])&&(c[j]<minn)){
				minn=c[j],jl=j;
			}
		if (jl==0) break;
		v[jl]=1;
		for (int j=1;j<=n;j++){
			c[j]=min(c[j],c[jl]+f[jl][j]);
		}
	}
	for (int i=1;i<=n;i++) printf("%d ",c[i]);
    return 0;
}