#include <vector>
#include <fstream>
#include <utility>
#include <queue>
 
using namespace std;
 
int vizitat[50005], distanta[50005];
 
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;
}