#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define inf 2000000000
int d[50003],poz[50003],distfi[50003];
bool use[50003];
struct nod
{
    int where,cost;
    nod *urm;
};
typedef nod *pnod;
pnod p,v[50003];
int n,m;
void ad(int x,int y,int cost)
{
    p=new nod;
    p->cost=cost;
    p->where=y;
    p->urm=v[x]->urm;
    v[x]->urm=p;
}
void upheap(int k)
{
    int o=d[k],q=poz[k];
    while(k>1 and d[k]<d[k/2])
    {
        d[k]=d[k/2];
        poz[k]=poz[k/2];
        k=k/2;
    }
    d[k]=o;
    poz[k]=q;
}
void swapp(int q,int r)
{
    int t=d[q];
    d[q]=d[r];
    d[r]=t;
    t=poz[q];
    poz[q]=poz[r];
    poz[r]=t;
}
void downheap(int k)
{
   int poz,i=1;
   do
   {
       poz=0;
       if(i*2<=k)
       {
           poz=i*2;
           if(i*2+1<=k and d[i*2+1]>d[i*2])
                poz=i*2+1;
           if(d[poz]>d[i])
           {
               poz=0;
           }
           else
            swapp(poz,i);
       }
   }while(poz);

}
int main()
{
    f>>n>>m;
    int i,x,y,c;
    for(i=1;i<=n+2;i++)
    {
        v[i]=new nod;
        v[i]->urm=0;
    }
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        ad(x,y,c);
    }
    int k=1;
    p=v[1]->urm;
    for(i=1;i<=n;i++)
        distfi[i]=inf;
    d[1]=p->cost;
    poz[1]=p->where;
    distfi[p->where]=p->cost;
    p=p->urm;
    while(p)
    {
        k+=1;
        d[k]=p->cost;
        poz[k]=p->where;
        upheap(k);
        distfi[p->where]=p->cost;
        p=p->urm;
    }
    int q;

    while(k)
    {
        q=poz[1];
        use[poz[1]]=1;
        p=v[q]->urm;
        swapp(1,k);
        downheap(k);
        k--;
        while(p)
        {
            if(distfi[p->where]>distfi[q]+p->cost)
            {
                distfi[p->where]=distfi[q]+p->cost;
               /* if(use[p->where]==0)
                {*/
                    k+=1;
                    d[k]=distfi[p->where];
                    poz[k]=p->where;
                    upheap(k);
               // }
            }
            p=p->urm;
        }
    }
    for(i=2;i<=n;i++)
    {
        if(distfi[i]!=inf)
            g<<distfi[i]<<" ";
        else
            g<<"0 ";
    }
}