#include<bits/stdc++.h>
using namespace std;
int e[1005][1005];
int dis[1005];
int vis[1005];
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
int tmp = e[u][v] ? e[u][v]:1e9;
e[u][v] = min(tmp,w);
}
for(int i=0;i<=n;i++){
dis[i] = 1e9;
}
dis[s]=0;
for(int i=1;i<n;i++){
int u=0;
for(int j=1;j<=n;j++){
if(!vis[j] && dis[j]<dis[u]){
u=j;
}
}
vis[u]=1;
for(int j=1;j<=n;j++){
if(e[u][j]){
int v=j;
int w=e[u][j];
if(dis[j]>dis[u]+w) dis[j]=dis[u]+w;
}
}
}
for(int i=1;i<=n;i++){
if(!(dis[i]==1e9)){
cout<<dis[i]<<" ";
}else{
cout<<"-1"<<" ";
}
}
return 0;
}
