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

using namespace std;

int a = 2147483647;

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

    int csucsokSzama, elekSzama;
    f >> csucsokSzama >> elekSzama;

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

    int x, y, z;
    for (int i = 0; i < elekSzama; i++)
    {
        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, 0));

    int hossz[csucsokSzama];
    fill_n(hossz, csucsokSzama, a);
    hossz[0] = 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 = 1; i < csucsokSzama; i++)
    {
        if (hossz[i] == a)
        {
            g << 0 << " ";
        }

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

    return 0;
}