#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,i,j,x,y,z,d[50001],t[50001],inc,sf,nod1;
struct nod{ int nr,val; nod *urm;};
nod *a[50001],*p,*prim,*ultim;

void pune(int x,int y,int z)
{
    p=new nod;
    p->nr=y;
    p->val=z;
    p->urm=0;
    p->urm=a[x];
    a[x]=p;
}
int main()
{
    f>>n>>m;
     for(i=1;i<=m;i++)
        f>>x>>y>>z,pune(x,y,z);

    for(i=2;i<=n;i++)
        d[i]=999999;

    prim=new nod;
    prim->nr=1;
    prim->urm=NULL;
    ultim=prim;

    while(prim)///coada vida
    {
        nod1=prim->nr;
        nod *q=a[nod1];
        while(q)
        {
            if(d[q->nr]>d[nod1]+q->val)
            {
                d[q->nr]=d[nod1]+q->val;
                t[q->nr]=nod1;

                nod *p1=new nod;
                p1->nr=q->nr;
                p1->urm=0;
                ultim->urm=p1;
                ultim=p1;
            }
            q=q->urm;
        }
        p=prim;
        prim=prim->urm;
        delete p;
    }
    for(i=2;i<=n;i++)
    {
        if(d[i]==999999)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    }
    return 0;
}