#include <iostream>
#include<fstream>
#include<vector>
#define infinity 9999999
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
struct nod
{
    int cost=infinity;
    bool a_fost_vizitat=false;
    vector<nod*>vecini;
    vector<int>muchii;
    void adauga_vecin(nod*p,int lungime)
    {
        vecini.push_back(p);
        muchii.push_back(lungime);
    }
};
nod noduri[50000];
int numar_noduri;
void read()
{
    int k,a,b,c;
    in>>numar_noduri>>k;
    for(int i=0; i<k; i++)
    {
        in>>a>>b>>c;
        noduri[a-1].adauga_vecin(&noduri[b-1],c);
    }
}
void dijkstra()
{
    noduri[0].cost=0;
    nod*aici=&noduri[0];
    bool end=false;
    while(1)
    {
        for(unsigned i=0; i<aici->vecini.size(); i++)
        {
            if(aici->vecini[i]->a_fost_vizitat==false)
                aici->vecini[i]->cost=min(aici->vecini[i]->cost,aici->cost+aici->muchii[i]);
        }
        aici->a_fost_vizitat=true;
        nod*urmatorul;
        end=true;
        int distanta_minima=infinity;
        for(unsigned i=0; i<numar_noduri; i++)
        {
            if(!noduri[i].a_fost_vizitat)
            {
                if(noduri[i].cost<distanta_minima)
                {
                    urmatorul=&noduri[i];
                    distanta_minima=noduri[i].cost;
                    end=false;
                }
            }
        }
        if(end)
            return;
        aici=urmatorul;

    }
}
int main()
{
    read();
    dijkstra();
    for(int i=1; i<numar_noduri; i++)
    {
        if(noduri[i].cost!=infinity)
            out<<noduri[i].cost<<" ";
        else
            out<<0<<" ";

    }
    return 0;
}