#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod{
    int nr,val,viz,fin;
nod *urm;};
nod *a[50001],*p,*q;
int n,m,i,j,x,y,z,v,nr,vf;
void pune(int x,int y,int z)
{
    p=new nod;
    p->nr=y;
    p->val=z;
    p->viz=0;
    p->fin=0;
    p->urm=0;
    if(!a[x])
        a[x]=p;
    else
    {
        q=a[x];
        while(q->urm)
            q=q->urm;
        q->urm=p;
    }
}
void cautaMin(int &vf)
{
        int m=99999;
        p=a[v];
        while(p)
        {
            if(a[p->nr]->viz==0&&p->val<m) ///daca nu e luat si are val minima
                m=p->val,vf=p->nr; ///retin val minima si varful in care se afla
            p=p->urm;
        }
}
void imbunatatireDrum(int vf)
{
    p=a[vf];
    while(p)
    {
        if(a[p->nr]->viz==0)
            if(a[vf]->fin+p->val<a[p->nr]->fin)
                a[p->nr]->fin=a[vf]->fin+p->val;
        p=p->urm;
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>z;
        pune(x,y,z);
    }
    v=1;
    a[v]->viz=1;

    p=new nod;
    p->viz=0;
    p->urm=0;
    for(i=2;i<=n;i++)
        if(!a[i])
            a[i]=p;
    p=a[v];
    while(p)
    {
        a[p->nr]->fin=p->val;
        p=p->urm;
    }
    for(i=2;i<=n;i++)
        if(a[i]->fin==0) a[i]->fin=99999;
    for(i=1;i<n;i++)
    {
        cautaMin(vf);
        a[vf]->viz=1;
        imbunatatireDrum(vf);
    }
    for(i=2;i<=n;i++)
    g<<a[i]->fin<<" ";
        return 0;
}