#include <iostream>
#include <cstdio>
#define Nmax 1000
#define Infinit 1001
using namespace std;
short int a[Nmax][Nmax];
int d[Nmax],pre[Nmax];
int n,i,start=1,j;
bool viz[Nmax];
void reading(int &n)
{
    int m;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        int x,y,z;
        scanf("%d %d %d",&x,&y,&z);
        a[x][y]=z;
    }
}
void init()
{
    for(i=1;i<=n;++i)
    {
        if (i==start) {d[i]=0;pre[i]=0;}
        else if (a[start][i]>0) d[i]=a[start][i];
        else d[i]=Infinit;
        if (i!=start) pre[i]=start;
        viz[i]=false;
    }
    viz[start]=true;
}
void dijsktra()
{
    reading(n);
    init();
    int k=start;
    int nod,j;
   for(j=1;j<=n;++j)
   {
         int minim=Infinit;
         for(i=1;i<=n;++i)
          if (!viz[i] && d[i]<minim) {minim=d[i];nod=i;}
            k=nod;
            viz[k]=1;
              for(i=1;i<=n;++i)
              if ((a[k][i]>0) && (d[k]+a[k][i]<d[i]))
               {
                     d[i]=d[k]+a[k][i];
                     pre[i]=k;
               }
   }

}
int main()
{
    dijsktra();
    for(i=2;i<=n;++i)
     if (d[i]==Infinit) printf("%d ",0);
      else printf("%d ",d[i]);
    return 0;
}