#include<fstream>
const int inf = 10000;

using namespace std;
const int maxn = 5000;
int a[maxn][maxn],n,m;



main(){
   freopen("dijkstra.in","r",stdin);
   freopen("dijkstra.out","w",stdout);
  
  int x,y,z;
  
 
    

scanf("%d %d",&n,&m);
 for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
	     a[k][i]=-1;
	   
for(int i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&z)	;
a[x][y]=z;
};/*
for(int k=1;k<=n;k++)
	for(int i=n;i>=1;i--)
		for(int j=1;j<=n;j++)
		 	if(a[i][k]+a[k][j]<a[i][j] )a[i][j]=a[i][k]+a[k][j];
		 	*/
 int i, j, k;
    for (k = 1; k <= n; k++)
        for (i = n; i >=1; i--)
            for (j = 1; j <= n; j++)
                if (a[i][k] != -1 && a[k][j] != -1 && (a[i][j] > a[i][k] + a[k][j] || a[i][j]==-1) && i != j) a[i][j] = a[i][k] + a[k][j];		 	
		 
 for(int k=2;k<=n;k++)printf("%d ",a[1][k]!=-1?a[1][k]:0);

//  printf("\n");

 
    
  
  
}