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

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

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

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