//#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
int n,m,kezd,k,maxi;
struct inti
{
    int* a;
    int poz;
};
vector <int> tav,poz;
vector <bool> latta;
struct adat
{
    int t,sz;
    adat* kov;
};
vector <adat*> x;
void be(adat* &s,int sz,int t)
{
    adat* p=new adat;
    p->t=t;
    p->sz=sz;
    p->kov=s;
    s=p;
}
vector <inti> v;
int be_kupac(vector <inti> &v,int &n,int &k,int poz1)
{
    int i=n+1;
    while (i>1 && *v[i/2].a>k)
    {
        v[i]=v[i/2];
        poz[v[i].poz]=i;
        i/=2;
    }
    v[i].a=&k;
    v[i].poz=poz1;
    n++;
    return i;
}
inti ki_kupac(vector <inti> &v,int &n)
{
    inti x=v[1];
    inti y=v[n];
    int i=1;
    n--;
    while (i<=n/2 && (*y.a>*v[2*i].a or *y.a>*v[2*i+1].a))
    if (2*i>n or *v[2*i].a<=*v[2*i+1].a)
    {
        v[i]=v[2*i];
        poz[v[i].poz]=i;
        i=2*i;
    }
    else
    {
        v[i]=v[2*i+1];
        poz[v[i].poz]=i;
        i=2*i+1;
    }
    v[i]=y;
    poz[v[i].poz]=i;
    return x;
}
void rendez_kupac(vector <inti> &v,int i)
{
    inti t;
    while (i>1 && *v[i].a<*v[i/2].a)
    {
        //Osszekoto Poz csere
        poz[v[i].poz]=i/2;
        poz[v[i/2].poz]=i;
        //Valtozo csere a kupacban
        t=v[i];
        v[i]=v[i/2];
        v[i/2]=t;
        i/=2;
    }
}
int minimum()
{
    if (k==0)
    return 0;
    inti a=ki_kupac(v,k);
    if (*a.a>maxi)
    maxi=*a.a;
    return a.poz;
}
void d(int kezd)
{
    tav.resize(n+1,99999999);
    latta.resize(n+1,0);
    poz.resize(n+1,0);
    tav[kezd]=0;
    poz[kezd]=be_kupac(v,k,tav[kezd],kezd);
    int p=minimum();
    int w;
    while (p)
    {
        adat* q=x[p];
        while (q!=NULL)
        {
            if (latta[q->sz])
            {
                q=q->kov;
                continue;
            }
            w=tav[p]+q->t;
            if (w<tav[q->sz])
            {
                if (tav[q->sz]==99999999)
                {
                    tav[q->sz]=w;
                    poz[q->sz]=be_kupac(v,k,tav[q->sz],q->sz);
                }
                else
                {
                    tav[q->sz]=w;
                    rendez_kupac(v,poz[q->sz]);
                }
            }
            q=q->kov;
        }
        latta[p]=1;
        p=minimum();
    }
}
int* keres(int csp,int k)
{
    adat* q=x[csp];
    while (q!=NULL)
    {
        if (q->sz==k)
        return &q->t;
        q=q->kov;
    }
    return NULL;
}
/*int kupac_rendez()
{
    cin>>n;
    v.resize(n+5);
    int q;
    for (int i=1;i<=n;i++)
    {
        cin>>q;
        be_kupac(v,i-1,q);
    }
    while (n)
    cout<<ki_kupac(v,n)<<" ";
}*/
int main()
{
    cin>>n>>m;
    int q,w,e;
    x.resize(n+1);
    int* r;
    for (int i=1;i<=m;i++)
    {
        cin>>q>>w>>e;
        r=keres(q,w);
        if (r==NULL)
        be(x[q],w,e);
        else
        if (e<*r)
        *r=e;
    }
    v.resize(n+1);
    k=0;
    d(1);
    for (int i=2;i<=n;i++)
    if (tav[i]!=99999999)
    cout<<tav[i]<<" ";
    else
    cout<<0<<" ";
}