#include <fstream>
#define inf 1001
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n, m, i, k, *a[50001], x0, s[50001], j, d[50001], prec[50001], vfsel;
void citire()
{
	int i, j, x, y, c;
	
	fin>>n>>m; x0=1;
	for (i=1;i<=n;i++)
		{   a[i]=(int*)realloc(a[i],sizeof(int));
			for  (j=1;j<=n;j++)
				a[i]=(int*)realloc(a[i],j*sizeof(int));
			a[i][j]=inf;
		}
	for (i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		a[x][y]=c;
	}
	for (i=1;i<=n;i++)
	{
		d[i]=a[x0][i];
		prec[i]=x0;
	}
	prec[x0]=0; s[x0]=1;
}
void afisare()
{
	int i, j, drum[101], k;
	for (i=1;i<=n;i++)
	{
		if (i!=x0)
		{
			if (d[i]==inf)
				fout<<0<<' ';
			else
			fout<<d[i]<<' ';
			/*drum[0]=i;
			k=0;
			while (prec[drum[k]]!=0)
			{
				k++;
				drum[k]=prec[drum[k-1]];
			}
			for (j=k;j>=0;j--)
				fout<<drum[j]<<' ';
			fout<<'\n';*/
		}
	}
}
int main()
{
	citire(); 
	//dijkstra
	int mini;
	for (j=1;j<=n-1;j++)
	{
		mini=inf;
		for (i=1;i<=n;i++)
			if(s[i]==0&&d[i]<mini)
			{
				mini=d[i];
				vfsel=i;
			}
		if (mini!=inf)
			{
				//restaurez d si prec
				s[vfsel]=1;
				for(i=1;i<=n;i++)
					if (s[i]==0)
						if (d[i]>d[vfsel]+a[vfsel][i])
						{
							d[i]=d[vfsel]+a[vfsel][i];
							prec[i]=vfsel;
						}
			}
		else break;
	}
	afisare();
	fout<<'\n';
	fout.close();
	return 0;
}