#include<iostream.h>
#include<fstream.h>
long long a[9000][9000];
int main()
{int i,j,k,n,m,x,y,z;

	ifstream f("dijkstra.in");
ofstream h("dijkstra.out");
f>>n>>m;

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


for(i=1;i<=m;i++)
{	f>>x>>y>>z;
a[x][y]=z;}
for(k=1;k<=n;k++)	
for(j=1;j<=n;j++)
 if(a[1][k]+a[k][j]<a[1][j]&&i!=k&&j!=k&&a[k][j]!=10000&&a[1][k]!=10000)	
	a[1][j]=a[1][k]+a[k][j];
for(i=2;i<=n;i++)
	h<<a[1][i]<<" ";


	return 0;}