#include <fstream>
#include <vector>

#define NMAX 50001
#define INF 10020200
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct matrice{vector<int> vecini,price;} mat[NMAX];
struct coada{int nod,price;};
vector<coada> co;
int _price[NMAX];
int n,m;

void cut1()
{
    int poz,fiu;
    coada tata;
    poz = 1;
    tata = co[co.size()-1]; co.pop_back();
    while(poz*2<co.size())
    {
        if(poz*2+1>co.size()-1 || co[poz*2].price<co[poz*2+1].price)
            fiu = poz*2;
        else
            fiu = poz*2+1;

        if(tata.price>co[fiu].price)
            co[poz] = co[fiu];
        else
            break;
        poz = fiu;
    }
    co[poz] = tata;
}

void up(int poz)
{
    coada aux;
    while(poz/2>=1 && co[poz].price < co[poz/2].price)
    {
        aux = co[poz];
        co[poz] = co[poz/2];
        co[poz/2] = aux;
        poz =poz/2;
    }
}

void bfs()
{
    coada a;
    a.nod = 1; a.price = 0;
    co.push_back(a);
    co.push_back(a);
    while(co.size()>1)
    {
        for(int i=0;i<mat[co[1].nod].vecini.size();i++)
            if(co[1].price + mat[co[1].nod].price[i] < _price[mat[co[1].nod].vecini[i]])
            {
                _price[mat[co[1].nod].vecini[i]] = a.price = co[1].price + mat[co[1].nod].price[i];
                a.nod = mat[co[1].nod].vecini[i];
                co.push_back(a);
                up(co.size()-1);
            }
        cut1();
    }
}

int main()
{
    int nod,vecin,price;
    fin>>n>>m;
    for(int i=1;i<m;i++)
    {
        fin>>nod>>vecin>>price;
        mat[nod].vecini.push_back(vecin);
        mat[nod].price.push_back(price);
    }

    for(int i=1;i<=n;i++)
        _price[i]=INF;
    _price[1]=0;

    bfs();

    for(int i=2;i<=n;i++)
    {
        if(_price[i]!=INF)
            fout<<_price[i]<<' ';
        else
            fout<<0<<' ';
    }
    return 0;
}