#include <fstream>
#define pinf = 900000 
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int i,j,n,m,a[5001][5001],x,y,c,k,d[50001],s[50001],t[50001],minn,poz;
int main()
{	fin>>n>>m;
	s[1]=1;
	for(i=1;i<=m;++i)
		{fin>>x>>y>>c;
		 a[x][y]=c;
		 if(x==1)
			 d[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(i=1;i<=n;++i)
		if(d[i]==0)
			d[i]=90000;
	for(k=2;k<=n;++k)
		{
			for(i=2;i<=n;++i)
				if(k!=i)
					{if(a[1][k]+a[k][i]<d[i])
						{
							d[i]=a[1][k]+a[k][i];
							a[1][k]=d[i];
						}
					}
				
		}

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