#include<fstream.h>
#define inf 0x3f3f

long long n , i , j , c , a[5000][5000] , d[5000] , t[5000] , u[5000] , sursa;
long long m , k;


void dijkstra(int sursa)
{
  int i , min , nod;
  memset(u , 0 , sizeof(u));
  memset(t , 0 , sizeof(t));
  memset(d, 0x3f , sizeof(d));
  d[sursa] = 0;
     while(1)
      {
	min = inf;
	nod = -1;
	 for(i = 1 ; i <= n ; i++)
	   if(!u[i] && min > d[i])
	    {
	      min = d[i];
	      nod = i;
	    }
	 if(min == inf)
	   break;
	u[nod] = 1;
	 for(i = 1 ; i <= n ; i++)
	   if(d[i] > d[nod] + a[nod][i])
	    {
	      d[i] = d[nod] + a[nod][i];
	      t[i] = nod;
	    }
     }
}



/*void scriu_drum(int i)
{
  if(t[i])
    scriu_drum(t[i]);
  cout<<i<<" ";
}*/



int main()
{
  ifstream f("dijkstra.in");
  ofstream g("dijkstra.out");
  f>>n>>m;
    for(i = 1 ; i <= n ; i++)
      for(j = 1 ; j <= n ; j++)
	if(i == j)
	  a[i][j] = 0;
    else
      a[i][j] = inf;
  for(k = 1 ; k <= m ; k++)
   {
     f>>i>>j>>c;
     a[i][j] = c;
   }
  f.close();
    dijkstra(1);
  for(i = 2 ; i <= n ; i++)
    g<<d[i]<<" ";
  /*cout<<endl;
  for(i = 1 ; i <= n ; i++)
   {
     scriu_drum(i);
     cout<<endl;
   }*/
 return 0;
}