#include <iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<math.h>

#define nmax 500073
const static int infinit=2000000;

using namespace std;

typedef struct
{
    int nod2;
    int dis;
}pereche;

int viz[nmax], dist[nmax], u=1, distaux[nmax], poz[nmax], h[nmax];
vector <pereche> v[nmax];

void vecini(int nod1,int nod2, int dis)
{
    pereche p;
    p.nod2=nod2;
    p.dis=dis;

    v[nod1].push_back(p);
}

void upheap (int nod)
{
     if (nod>1)
     if (distaux[h[nod/2]]>distaux[h[nod]])
         {
             swap(poz[h[nod/2]],poz[h[nod]]);
             swap(h[nod/2],h[nod]);

             upheap(nod/2);
         }
}

void downheap( int nod)
{
     int fiu;
     if (nod*2<=u) {
         fiu=nod*2;
         if (nod*2+1<=u && distaux[h[fiu]]>distaux[h[nod*2+1]])
             fiu=fiu+1;

         if (distaux[h[fiu]]<distaux[h[nod]])
         {
                swap(poz[h[nod]],poz[h[fiu]]);
                swap(h[fiu],h[nod]);

                downheap(fiu);
         }
     }
}


void insert_heap(int nod)
{
    h[++u]=nod;
    poz[nod]=u;
    upheap(u);
}

void stergere(int nod)
{
    distaux[nod]=infinit;
    downheap(poz[nod]);
}


void distante(int a, int b, int c)
{

    int distance=dist[a]+c;
    if (dist[b]>distance)  {
                              dist[b]=distance;
                              distaux[b]=distance;
                              insert_heap(b);
                           }



}

void parcurgere(int n)
{
   int nod;
   for (int j=1;j<=n;j++)
   {
        nod=h[1];
        viz[nod]=1;
        stergere(nod);

        for (unsigned int i=0;i<v[nod].size();i++)
            if (!viz[v[nod][i].nod2]) distante(nod,v[nod][i].nod2,v[nod][i].dis);
   }

}


int main()
{
    int a,b,c,n,m;

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    cin>>n>>m;

    for (int i=1;i<=m;i++)
        {
            cin>>a>>b>>c;
            vecini(a,b,c);
        }



   for (int i=2;i<=n;i++)
        dist[i]=infinit;

   dist[1]=0;
   distaux[1]=0;
   h[1]=1;
   poz[1]=1;

   parcurgere(n);

   for (int i=2;i<=n;i++)
       if (dist[i]==infinit)  cout<<0<<" ";
            else  cout<<dist[i]<<" ";



    return 0;
}