#include<bits/stdc++.h>
using namespace std;
int book[1001],e[1001][1001],dis[1001];
int i,j,n,m,inf=99999999,t1,t2,t3,s,f,u,miin;
int main(){
cin>>n>>m>>s;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(i==j) e[i][j]=0;
else e[i][j]=inf;
}
}//chushi
for(j=1;j<=m;j++){
cin>>t1>>t2>>t3;
e[t1][t2]=t3;
}//durubian
for(i=1;i<=n;i++){
dis[i]=e[s][i];
}//dischushihua
for(i=1;i<=n;i++){
book[i]=0;
}//chushihuabook
book[s]=1;
for(i=1;i<n;i++){
miin=inf;
for(j=1;j<=n;j++){
if (book[j]==0&&dis[j]<miin) miin=dis[j];u=j;
}
book[u]=1;
for(j=1;j<=n;j++){
if(e[u][j]+dis[u]<dis[j]&&e[u][j]<inf)//联通
{
dis[j]=dis[u]+e[u][j];
}
}
}
for(i=1;i<=n;i++) {
cout<<dis[i]<<' ';
}
return 0;
}
rt,我感觉最近我脑抽