#include<bits/stdc++.h>
#define INF 2147483637

using namespace std;
struct edge
{
    int to;
    int weight;
};
struct node
{
    int id;
    int ndis;
    node(int x,int y)
    {
        id=x;
        ndis=y;
    }
    bool operator <(const node&a) const{
        return ndis>a.ndis;
    }
};
priority_queue<node> q;
vector<edge> b[20005];

int dis[10005];
int vis[10005];
int n,m,a;
void Dij(int x)
{
    dis[x]=0;
    vis[x]=1;
    q.push(node(x,dis[x]));
    while(!q.empty())
    {
        int v=q.top().id;
        vis[v]=1;
    for(int i=0;i<b[v].size();i++)
    {
       int t=b[v][i].to;
       if(!vis[t]&&dis[t]>dis[v]+b[v][i].weight)
       {
           dis[t]=dis[v]+b[v][i].weight;
           q.push(node(t,dis[t]));
       }

    }
    q.pop();
    }

}
int main()
{
  cin>>n>>m>>a;
  int x,y,z;
  for(int i=1;i<=n;i++) dis[i]=INF;
  for(int i=1;i<=m;i++)
  {
      cin>>x>>y>>z;
      b[x].push_back((edge){y,z});
  }
  Dij(a);
  for(int i=1;i<=n;i++)
    cout<<dis[i]<<" ";
  return 0;
}