#include<fstream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
long n,m;
int mat[500][500];
void citire()
{in>>n>>m;
 int i,j,x,y,z;
  for (i=0;i<n;i++)
	  for (j=0;j<n;j++)
		  mat[i][j]=32000;
  for (i=0;i<m;i++)
     {in>>x>>y>>z;
      mat[x-1][y-1]=z;
     }
  /* afisare
  for (i=0;i<n;i++)
      {for (j=0;j<n;j++)
		  out<<mat[i][j]<<" ";
       out<<endl;
      }
  */
}
void dijkstra()
{int i,j,nod,min,s[500],t[500],d[500];
 for (i=0;i<n;i++)
	 s[i]=t[i]=d[i]=0;
 s[0]=1;
 for (i=1;i<n;i++)
 {d[i]=mat[0][i]; 
  if (d[i]<32000) t[i]=0;
 }
 for (i=0;i<n-1;i++)
 {min=32000;
   for (j=1;j<n;j++)
	   if (!s[j]&&d[j]<min) {min=d[j]; nod=j;}
   s[nod]=1;
   for (j=1;j<n;j++)
	   if (d[j]>d[nod]+mat[nod][j]) {d[j]=d[nod]+mat[nod][j]; t[j]=nod;}
 }
 for (i=1;i<n;i++)
	 out<<d[i]<<" ";
}
int main()
{	citire();
    dijkstra();
	return 0;
}