#include <fstream>
#include <vector>

using namespace std;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

#define Max 99999999999
#define f first
#define s second

struct adat
{
    bool l;
    long long hossz=Max,hol;
    vector<pair<int,int>>ut;
};
vector<adat>x;

struct uthossz
{
    long long ki,ut;
};
vector<uthossz>kupac;
uthossz k;

long long n,m,a,b,c,i;

void beszur(vector<uthossz>&kupac,int ki,int ut)
{
    kupac.push_back({ki,ut});
    int akt=kupac.size()-1;

    while(akt!=0 && kupac[akt/2].ut>ut)
    {
        x[kupac[akt/2].ki].hol=akt;
        kupac[akt]=kupac[akt/2];
        akt/=2;
    }
    x[ki].hol=akt;
    kupac[akt].ut=ut;
    kupac[akt].ki=ki;
}

void torol(vector<uthossz>&kupac,int poz)
{
    x[kupac[poz].ki].hol=0;
    kupac[poz]=kupac.back();
    x[kupac[poz].ki].hol=poz;
    kupac.pop_back();
    int p=0;
    while(p!=poz)
    {
        p=poz;
        if(p*2<kupac.size() && kupac[p*2].ut<kupac[poz].ut)
            poz=p*2;
        if(p*2+1<kupac.size() && kupac[p*2+1].ut<kupac[poz].ut)
            poz=p*2+1;

        x[kupac[poz].ki].hol=p;
        x[kupac[p].ki].hol=poz;

        swap(kupac[p],kupac[poz]);
    }
}

void atir(vector<uthossz>&kupac, int poz, int ut, int ki)
{
    kupac[poz].ut=ut;
    int akt=poz;

    while(akt!=0 && kupac[akt/2].ut>ut)
    {
        x[kupac[akt/2].ki].hol=akt;
        kupac[akt]=kupac[akt/2];
        akt/=2;
    }
    x[ki].hol=akt;
    kupac[akt].ut=ut;
    kupac[akt].ki=ki;

    int p=0;
    while(p!=poz)
    {
        p=poz;
        if(p*2<kupac.size() && kupac[p*2].ut<kupac[poz].ut)
            poz=p*2;
        if(p*2+1<kupac.size() && kupac[p*2+1].ut<kupac[poz].ut)
            poz=p*2+1;

        x[kupac[poz].ki].hol=p;
        x[kupac[p].ki].hol=poz;

        swap(kupac[p],kupac[poz]);
    }
}

int main()
{
    cin>>n>>m;
    x.resize(n+1);
    for(i=1;i<=m;++i)
    {
        cin>>a>>b>>c;
        x[a].ut.push_back({b,c});
    }

    beszur(kupac,1,0);

    while(!kupac.empty())
    {
        k=kupac.front();
        torol(kupac,0);

        x[k.ki].l=true;
        x[k.ki].hossz=k.ut;

        for(auto e : x[k.ki].ut)
        if(!x[e.f].l && x[e.f].hossz>(e.s+x[k.ki].hossz))
        {
            if(x[e.f].hossz!=Max) atir(kupac,x[e.f].hol,e.s+x[k.ki].hossz, e.f);
            else beszur(kupac,e.f,e.s+x[k.ki].hossz);
            x[e.f].hossz=e.s+x[k.ki].hossz;
        }
    }

    for(i=2;i<=n;++i)
    if(x[i].hossz==Max) cout<<"0 ";
    else cout<<x[i].hossz<<" ";

    return 0;
}