#include<fstream.h>
#define NMAX 2000
#define INF 5000000
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int a[NMAX][NMAX];
int d[NMAX], viz[NMAX], n;

void citeste()
{
	int i, m, x, y, c, j;
	f>>n>>m;
	for (i=1; i<=n; ++i) 
		for (j=1; j<=n; ++j)
			a[i][j]=INF;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y>>c;
		a[x][y]=c;
	}
	
}

void solve()
{
	int min, i, imin=1;
	viz[1]=1;
	for (i=1; i<=n; ++i)
		d[i]=a[1][i];
	while (imin)
	{
		min=INF;imin=0;
		for(i=2; i<=n; ++i)
			if(min>d[i] && !viz[i]) {min=d[i];imin=i;}
		if (min!=INF)
		{
			viz[imin]=1;
			for (i=2; i<=n; ++i)
				if (!viz[i] && d[i]>d[imin]+a[imin][i])
					d[i]=d[imin]+a[imin][i];
		}
	}
}

void scrie()
{
	int i;
	for(i=2; i<=n; ++i)
		if (d[i]<INF) g<<d[i]<<" ";
	else g<<"0 ";
	g<<"\n";
}
	

int main()
{
	citeste();
	solve();
	scrie();
	f.close();
	g.close();
	return 0;
}