#include<bits/stdc++.h>
using namespace std;
const int maxn=1000010;
struct e{
long long u,v,w,nxt;
}edge[maxn];
long long head[maxn],tot,n,m,s,dis[maxn],vis[maxn];
struct node{
long long w,now;
inline bool operator<(const node&x)const
{
return w>x.w;
}
};
priority_queue<node> q;
void add(long long u,long long v,long long w){
edge[++tot].u=u;
edge[tot].v=v;
edge[tot].w=w;
edge[tot].nxt=head[u];
head[u]=tot;
}
void dij(){
memset(dis,127/3,sizeof(dis));
dis[s]=0;
q.push(node{0,s});
while(!q.empty()){
node x=q.top();
q.pop();
long long u=x.now;
vis[u]=1;
for(long long i=head[u];i;i=edge[i].nxt){
long long v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
q.push(node{dis[v],v});
}
}
}
}
int main(){
cin>>n>>m>>s;
for(long long i=1;i<=m;i++)
{
long long u,v,w;
cin>>u>>v>>w;
add(u,v,w);
}
dij();
for(long long i=1;i<=n;i++)
cout<<dis[i]<<" ";
return 0;
}