#include <iostream>
#include <fstream>
#define oo 9999999

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int a[1000][1000], viz[50000], dist[5000], n, m, st, min1, im;
int main()
{
    int i, j, x, y, c;
    f>>n;
    f>>m;
    for (i=1; i<=m; i++)
      {
          f>>x>>y>>c;
          a[x][y]=c;
      }
    for (i=1; i<=n; i++)
      for (j=1; j<=n; j++)
      {
         // f>>a[i][j];
          if (a[i][j]==0 && i!=j) a[i][j]=oo;
      }

      st=1;

      viz[st]=1;

      for (i=1; i<=n; i++)
        dist[i]=a[1][i];

      for (i=2; i<=n; i++)
      {
          min1=oo;
          for (j=1; j<=n; j++)
            if (dist[j]<min1 && viz[j]==0)
              {
                  min1=dist[j];
                  im=j;
              }
          viz[im]=1;
          for (j=1; j<=n; j++)
            if (viz[j]==0 && dist[im]+a[im][j]<dist[j])
              if (a[im][j]<oo) dist[j]=dist[im]+a[im][j];
      }
      for (i=2; i<=n; i++) g<<dist[i]<<" ";
    return 0;
}