#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define inf 2000000000
struct nod
{
    int where,cost;
    nod *urm;
};
typedef nod *pnod;
pnod v[50003],p;
void ad(int x,int y,int cost)
{
    p=new nod;
    p->where=y;
    p->cost=cost;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
int n,m;
int dist[50003],poz[50003],h[50003];
void swa(int x,int y)
{
    int t;
    t=poz[x];
    poz[x]=poz[y];
    poz[y]=t;
}
/*void upheap(int inc)
{
    int t=poz[inc],q=inc;
    while(inc>1 and dist[poz[inc]]<dist[poz[inc/2]])
    {
        h[poz[inc]]=inc/2;
        h[poz[inc/2]]=inc;
        swa(inc,inc/2);
        inc/=2;
    }

  //  poz[inc]=t;
   // h[poz[inc]]=q;

}*/

void upheap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( dist[ poz[tata] ] > dist[ poz[what] ] )
        {
            h[ poz[what] ] = tata;
            h[ poz[tata] ] = what;

            swa(tata, what);

            what = tata;
        }
        else
            what = 1;
    }
}
int k;
/*void downheap(int fi)
{
    int now;
    do
    {
        now=0;
        if(fi*2<=k)
        {
            now=fi*2;
            if(now+1<=k and dist[poz[now+1]]<dist[poz[now]])
                now+=1;
            if(dist[now]>=dist[fi])
                now=0;
            else
            {
                h[poz[now]]=fi;
                h[poz[fi]]=now;
                swa(now,fi);
                fi=now;
            }
        }
    }while(now);
}*/


void downheap(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( dist[ poz[f + 1] ] < dist[ poz[f] ] )
                    ++f;
        }
        else
            return;

        if ( dist[ poz[what] ] > dist[ poz[f] ] )
        {
            h[ poz[what] ] = f;
            h[ poz[f] ] = what;

            swa(what, f);

            what = f;
        }
        else
            return;
    }
}
int main()
{
    int i,x,y,c;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
        dist[i]=inf;
        h[i]=-1;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
    }
    p=v[1]->urm;
    dist[1]=0;
    h[1]=0;
    while(p)
    {
        k+=1;
        dist[p->where]=p->cost;
        poz[k]=p->where;
        h[p->where]=k;
        upheap(k);
        p=p->urm;
    }
    int minim;
    while(k)
    {
        minim=poz[1];
        swa(1,k);
        h[poz[1]]=1;
        k--;
        downheap(1);

        p=v[minim]->urm;
        while(p)
        {
            if(dist[p->where]>dist[minim]+p->cost)
            {
                dist[p->where]=dist[minim]+p->cost;
                if(h[p->where]==-1)
                {
                    k+=1;
                    poz[k]=p->where;
                    h[p->where]=k;
                    upheap(k);
                }
                else
                {
                    upheap(h[k]);
                }
            }
            p=p->urm;
        }
    }
    for(i=2;i<=n;i++)
        if(dist[i]==inf)
            g<<"0 ";
        else
            g<<dist[i]<<" ";
    g<<'\n';
    return 0;
}