#include <iostream>
#include <fstream>
#include <list>
#include <queue>

using namespace std;

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");

    int csucsokSzama, start;
    f >> csucsokSzama >> start;
    start--;

    list< pair<int, int> > csucsok[csucsokSzama];
    list< pair<int, int> > :: iterator it;

    int x, y, z;
    while (f >> x >> y >> z)
    {
        csucsok[x - 1].push_back(make_pair(z, y - 1));
    }

    priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair <int, int> > > sor;
    sor.push(make_pair(0, start));

    int hossz[csucsokSzama];
    fill_n(hossz, csucsokSzama, INT_MAX);
    hossz[start] = 0;

    int elottem[csucsokSzama];
    fill_n(elottem, csucsokSzama, -1);

    bool jart[csucsokSzama];
    fill_n(jart, csucsokSzama, false);

    pair<int, int> elem;
    while (!sor.empty())
    {
        elem = sor.top();
        sor.pop();

        if (jart[elem.second] == true)
        {
            continue;
        }

        jart[elem.second] = true;

        for(it = csucsok[elem.second].begin(); it != csucsok[elem.second].end(); it++)
        {
            if (hossz[it->second] > hossz[elem.second] + it->first)
            {
                hossz[it->second] = hossz[elem.second] + it->first;
                elottem[it->second] = elem.second;

                sor.push(*it);
            }
        }
    }

    for (int i = 0; i < csucsokSzama; i++)
    {
        if (hossz[i] == INT_MAX)
        {
            cout << -1 << " ";
            g << -1 << " ";
        }

        else
        {
            cout << hossz[i] << " ";
            g << hossz[i] << " ";
        }
    }
    cout << ' ';

//    for (int i = 0; i < csucsokSzama; i++)
//    {
//        cout << i + 1 << " ";
//    }
//    cout << endl;
//
//    for (int i = 0; i < csucsokSzama; i++)
//    {
//        cout << hossz[i] << " ";
//    }
//    cout << endl;
//
//
//    for (int i = 0; i < csucsokSzama; i++)
//    {
//        cout << elottem[i] + 1 << " ";
//    }
//    cout << endl;

    return 0;
}