#include <fstream>
#include <vector>
#include <queue>

#define NMAX 100005
#define INF 1000000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct Arc
{
    int vf, c;
};

int n, start;
int x, y, c;
vector<Arc> g[NMAX];
int dmin[NMAX], pre[NMAX]; bool uz[NMAX];
int minim, vfmin;
int i, j;

class ComparVf
{
public:
    bool operator() (const int& x, const int& y)
    {
        return dmin[x] > dmin[y];
    }
};
priority_queue<int, vector<int>, ComparVf> h;

void afisareDrum(int);

int main()
{
    ///Citire
    fin >>n>>start;
    while (fin >>x>>y>>c)
        g[x].push_back({y, c});

    ///Dijkstra
    uz[start] = 1;
    for (i = 1; i <= n; ++i)
    {
        pre[i] = start;
        dmin[i] = INF;
    }
    pre[start] = 0; dmin[start] = 0;

    //parcurgem lista de adiacenta a lui start
    for (i = 0; i < g[start].size(); ++i)
        dmin[g[start][i].vf] = g[start][i].c;

    h.push(g[start][0].vf);

    while (!h.empty())
    {
        vfmin = h.top(); h.pop();
        minim = dmin[vfmin];

        uz[vfmin] = 1;
        for (j = 0; j < g[vfmin].size(); ++j)
            if (!uz[g[vfmin][j].vf])
                if (dmin[g[vfmin][j].vf] > minim + g[vfmin][j].c)
                {
                    dmin[g[vfmin][j].vf] = minim + g[vfmin][j].c;
                    pre[g[vfmin][j].vf] = vfmin;
                    h.push(g[vfmin][j].vf);
                }
    }

    for (i = 1; i <= n; ++i)
        if (dmin[i] == INF) fout <<-1<<' ';
        else fout <<dmin[i]<<' ';
    fout <<'\n';

    //afisareDrum(1);
    //fout <<'\n';
    fout.close();
    return 0;
}

void afisareDrum(int x)
{
    if (x == start)
    {
        fout <<start<<' ';
        return;
    }
    afisareDrum(pre[x]);
    fout <<x<<' ';
}