#include <fstream>
#include <iostream>
using namespace std;


struct list{
    int v,c;
    list *adr;
};

void add(int i, int j, list *&p)
{
    list *tmp;
    tmp=new list;
    tmp->v=i;
    tmp->c=j;
    tmp->adr=p;
    p=tmp;
}


unsigned int d[50001],pr[50001],q[250001];
list *l[50001],*p;

int main()
{   int i,n,m,a,b,dist,fi=1,la=0;
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        l[i]=new list;
        l[i]->adr=NULL;
    }
    for(i=1;i<=m;i++)
    {
    f>>a>>b>>dist;
    add(a,dist,l[b]);
    add(b,dist,l[a]);
    }

   /* for(i=1;i<=n;i++)
    {
        g<<i<<'\n';
        p=l[i];
        while(p->adr!=NULL)
        {
            g<<p->v<<' '<<p->c<<'\n';
            p=p->adr;
        }
    }
*/

    for(i=2;i<=n;i++) d[i]=2100000000;
    q[++la]=1;
    //ve[1]=1;
    p=l[q[fi]];
    while(fi<=la)
    {
        if(p->adr!=NULL)
        {
            if(d[q[fi]]+p->c < d[p->v])
            {
                q[++la]=p->v;
                d[p->v]=d[q[fi]]+p->c;
                pr[p->v]=q[fi];
            }
            p=p->adr;
        }
        else {fi++; p=l[q[fi]];}
    }

    for(i=2;i<=n;i++) g<<d[i]<<' ';
    g<<'\n';
   // for(i=2;i<=n;i++) g<<pr[i]<<' ';
   // g<<'\n';
    f.close();
    g.close();
    return 0;
}