#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int NMAX = 60000;
const int oo = 10000000;

int noduri, muchii;
int distanta[NMAX];
bool InCoada[NMAX];
struct comparaDistante
{
    bool operator()(int a, int b)
    {
        return distanta[a] > distanta[b];
    }
};
vector <pair<int, int> > graf[NMAX];
priority_queue < int, vector<int>, comparaDistante> coada;
void citire()
{
    f>>noduri>>muchii;
    for(int i=1;i<=muchii;i++)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        graf[x].push_back(make_pair(y,cost));

    }
}
void Dijkstra(int nodStart)
{
    for(int i=1;i<=noduri;i++)
        distanta[i] = oo;
    distanta[nodStart] = 0;
    coada.push(nodStart);
    InCoada[nodStart] = true;
    while(!coada.empty())
    {
        int nodCurent = coada.top();
        coada.pop();
        InCoada[nodCurent] = false;
        for(size_t i = 0; i< graf[nodCurent].size();i++)
        {
            pair<int,int> pereche = graf[nodCurent][i];
            int vecin = pereche.first;
            int cost = pereche.second;
            if(distanta[nodCurent] + cost < distanta[vecin])
            {
                distanta[vecin] = distanta[nodCurent] + cost;
                if(InCoada[vecin] == false)
                {
                    coada.push(vecin);
                    InCoada[vecin] = true;
                }
            }
        }
    }

}
void afisare()
{
    for(int i = 2;i<=noduri;i++)
        if(distanta[i] != oo)
            g<<distanta[i]<<" ";
        else
            g<<"0"<<" ";
}
int main()
{
    citire();
    Dijkstra(1);
    afisare();
    return 0;
}