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

using namespace std;

int vizitat[50001], distanta[50000];

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

    int i;
    int nr_noduri, nr_muchii, nod_plecare, nod_destinatie, pondere, nod_curent, nod_aux, cost;

    vector<pair<int,int> > graf[50001];
    pair<int,int> pereche;
    queue<int> coada;

    f >> nr_noduri >> nr_muchii;

    for(i = 0; i < nr_muchii; i++)
        {
            f >> nod_plecare >> nod_destinatie >> pondere;
            pereche = make_pair(nod_destinatie,pondere);

            graf[nod_plecare].push_back(pereche);
        }

    distanta[1] = 0;
    for(i = 2; i <= nr_noduri; i++)
        distanta[i] = 9999;

    coada.push(1);
    vizitat[1] = 0;
    while(!coada.empty())
        {
            nod_curent = coada.front();
            vizitat[nod_curent] = 0;
            coada.pop();

            for(i = 0; i < graf[nod_curent].size(); i++)
                {
                    nod_aux = graf[nod_curent][i].first;
                    cost = graf[nod_curent][i].second;

                    if(distanta[nod_aux] > distanta[nod_curent] + cost)
                        {
                            distanta[nod_aux] = distanta[nod_curent] + cost;
                            if(!vizitat[nod_aux])
                                {
                                    vizitat[nod_aux] = 1;
                                    coada.push(nod_aux);
                                }
                        }
                }
        }

    for(i = 2; i <= nr_noduri; i++)
        if(distanta[i] == 9999)
            g << 0 << " ";
        else
            g << distanta[i] << " ";

    return 0;
}