#include <bits/stdc++.h>

using namespace std;
const int NMAX=1e5+10;
const int INF=2e9+10;
vector<pair<int,int>> G[NMAX];
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int d[NMAX];
int nod1,nod2,cost,n,m,p;
int main()
{
    fin >> n >> m >> p;

    for (int i=0;i<m;i++) {
        fin >> nod1 >> nod2 >> cost;
        G[nod1].push_back(make_pair(nod2,cost));
    }

    for (int i=1;i<=n;i++)
        d[i]=INF;
    d[p]=0;
    set<pair<int,int>> h;
    h.insert(make_pair(0,p));
    while (!h.empty()) {
        nod1=h.begin()->second;
        h.erase(h.begin());
        for (vector<pair<int, int>>::iterator it = G[nod1].begin(); it != G[nod1].end(); it++){
            nod2 = it->first;
            cost = it->second;
            if (d[nod2] > d[nod1] + cost) {
                if (d[nod2] != INF)
                    h.erase(h.find(make_pair(d[nod2],nod2)));
                d[nod2] = d[nod1] + cost;
                h.insert(make_pair(d[nod2],nod2));
            }
        }
    }

    for (int i=1;i<=n;i++) {
            if (d[i] == INF)
                d[i]=-1;
            fout << d[i] << " ";
    }
    return 0;
}