#include <fstream>
#define pinf = 900000 
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int i,j,n,m,a[10001][10001],x,y,c,k;
int main()
{	fin>>n>>m;
	for(i=1;i<=m;++i)
		{fin>>x>>y>>c;
		 a[x][y]=c;
		}
	for(i=1;i<=n;++i)
		for(j=1;j<=n;++j)
			if(i!=j&&a[i][j]==0)
				a[i][j]=90000;
	
	
	for(k=2;k<=n;++k)
		{
			for(i=2;i<=n;++i)
				if(k!=i)
					{if(a[1][k]+a[k][i]<a[1][i])
							a[1][i]=a[1][k]+a[k][i];
					}
				
		}

	for(i=2;i<=n;++i)
		 fout<<a[1][i]<<" ";
	return 0;
}