#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f

using namespace std;

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

class Graf
{
private:

    int numar_noduri, numar_arce;
    vector <vector <pair<int, int>>> lista_adiacenta;

public:

    void dijkstra1();

    vector <int> dijkstra2(const int a)
    {
        int b;
        vector <int> lungime_drum(numar_noduri, INF);
        vector <bool> pq(numar_noduri + 1, 0);
        priority_queue <pair <int, int>, vector <pair <int, int>>, greater<pair<int, int>>> coada;
        lungime_drum[a] = 0;
        coada.push(make_pair(0, a));

        while(!coada.empty())
        {
            b = coada.top().second;
            coada.pop();

            if(pq[b] == 0)
            {
                pq[b] = 1;
                for(int i = 1; i < lista_adiacenta[b].size(); i++)
                    if(lungime_drum[lista_adiacenta[b][i].first] > lungime_drum[b] + lista_adiacenta[b][i].second)
                {
                    lungime_drum[lista_adiacenta[b][i].first] = lungime_drum[b] + lista_adiacenta[b][i].second;
                    coada.push(make_pair(lungime_drum[lista_adiacenta[b][i].first], lista_adiacenta[b][i].first));
                }
            }
        }

        return lungime_drum;

    }
};

void Graf :: dijkstra1()
{
    int nod1, nod2, lungime_arc;
    vector <pair <int, int>> lista(1, make_pair(-1, -1));

    fin >> numar_noduri >> numar_arce;

    for(int i = 0; i <= numar_noduri + 1; i++)
        lista_adiacenta.push_back(lista);

    for(int i = 0; i < numar_arce; i++)
    {
        fin >> nod1 >> nod2 >> lungime_arc;
        lista_adiacenta[nod1].push_back(make_pair(nod2, lungime_arc));
    }

    vector <int> lungime_drum = dijkstra2(1);

    for(int i = 2; i <= numar_noduri; i++)
        if(lungime_drum[i] != INF)
            fout << lungime_drum[i] << " ";
        else
            fout << 0 << " ";
}

int main()
{
    Graf x;
    x.dijkstra1();

    fin.close();
    fout.close();

    return 0;
}