#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,nod;
struct nod1{
int nr,val;
nod1 *urm;};

nod1 *a[50001],*p,*prim,*ultim;
void pune(int x,int y,int z)
{
    p=new nod1;
    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=1;i<=n;i++)
      {
          g<<"vecinii "<<i<<" ";
      p=a[i];
      while(p){g<<p->nr<<" ";p=p->urm;}
      }
      **/

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

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

    while(prim&&ultim)///coada vida
    {
        p=prim;
         nod=p->nr;

        prim=prim->urm;
        delete p;

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

                if(prim==NULL)
                {prim= new nod1;
                prim->nr=q->nr;prim->urm=NULL;ultim=prim;
                }
                else
                {
                     p=new nod1;
                p->nr=q->nr;
                p->urm=0;
                ultim->urm=p;
                ultim=p;

            }
            }
            q=q->urm;
        }

          }
    for(i=2;i<=n;i++)
        if(d[i]==999999) g<<"0 ";
    else g<<d[i]<<" ";
    return 0;
}