#include <fstream.h>

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

long int n, m, x, y, c[10000][10000], cost, viz[100000], tata[100000], d[100000], INF=32000;


void bellmanford (int);

int main ()
{
  int i, j;
  fin>>n>>m;
  for (i=1; i<=n; i++)
    for (j=1; j<=n; j++)
      c[i][j]=INF;
  for (i=1; i<=m; i++)
  {
    fin>>x>>y>>cost;
    c[x][y]=cost;
  }
  bellmanford (1);
  for (i=2; i<=n; i++)
    fout<<d[i]<<' ';
  fin.close();
  fout.close ();
  return 0;
}

/*void bellmanford(int x)
{
  int inc, sf, q[100], i;
  inc=sf=1;
  q[inc]=x;
  for (i=1; i<=n; i++)
	d[i]=INF;
  d[x]=0;
  while (inc<=sf)
  {
	  x=q[inc++];
	  for (i=1; i<=n; i++)
		  if (i!=x)
			  if (d[i]>d[x] + c[x][i])
        {
          d[i]=d[x] + c[x][i];
				  q[++sf]=i;
        }
  }
}*/

//varianta de pe arhiva campion
void bellmanford (int x0) 
{
  int i, j, k;
  for (i=1; i<=n; i++) 
    d[i] = INF;
  d[x0] = 0;
  for (i=1; i<=n; i++) 
  {
    for (j=1; j<=n; j++)
      for (k=1; k<=n; k++)
        if (d[j]!=INF && c[j][k]!=INF)
          if (d[k]>d[j]+c[j][k])
          {
            d[k] = d[j]+c[j][k];
            tata[k] = j;
          }
  } 
}