#include <fstream>
#include <queue>
#include <iostream>
#include <string.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
typedef pair <int,int> ipair;
int n,m,source;
int dist[100001];
vector <ipair> v[100001];
bool found[100001];
priority_queue<ipair,vector<ipair>,greater<ipair>> q;
int main()
{
    f>>n>>m>>source;
    int a,b,d;
    for(int i=1;i<=m;i++){ f>>a>>b>>d;
                           ipair x;
                           x.first=d;
                           x.second=b;
                           v[a].push_back(x);
                           x.second=a;
                           v[b].push_back(x);
                         }
    int l=0;
    ipair x1;
    memset(dist,-1,sizeof(dist));
    x1.first=0;
    x1.second=source;
    q.push(x1);
    while(q.size() && l!=n){ ipair x=q.top();
                       q.pop();
                       if(!found[x.second])
                     {found[x.second]=1;
                      l++;
                      dist[x.second]=x.first;
                      for(int i=0;i<v[x.second].size();i++){ ipair x2;
                                                              x2=v[x.second][i];
                                                              x2.first+=x.first;
                                                              if(!found[x2.second])
                                                              q.push(x2);
                                                           }

                      }

                         }
    for(int i=1;i<=n;i++)g<<dist[i]<<" ";
    g<<'\n';
    return 0;
}