#include <fstream>
using namespace std;
#define DIM 2005
#define OO (1<<30)-1

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

int N, M, C[DIM][DIM], D[DIM], T[DIM], viz[DIM];

void dijkstra()
{
	int i, k, m;
	
	viz[1] = 1;
	for (i = 1; i <= N; i++)
	{	
		if (C[1][i] != OO)
			T[i] = 1;
		D[i] = C[1][i];	
	}
	
	T[1] = 0;
	while (1)
	{
		m = OO;
		for (i = 1; i <= N; i++)
			if (!viz[i] && D[i] < m)
			{
				m = D[i];
				k = i;
			}
		if (m == OO)
			break;
		viz[k] = 1;
		for (i = 1; i <= N; i++)
			if (!viz[i] && D[i] > D[k] + C[k][i])
			{
				D[i] = D[k] + C[k][i];
				T[i] = k;
			}
	}	
}

int main()
{
	fi >> N >> M;
	for (int i = 1, j; i <= N; i++)
		for (j = 1; j <= N; j++)
			C[i][j] = OO;
	for (int i = 0, x, y, c; i < M; i++)
	{
		fi >> x >> y >> c;
		C[x][y] = c;
	}
	dijkstra();
	for (int i = 2; i <= N; i++)
		if (D[i] == OO)
			fo << "0 ";
		else
			fo << D[i] << ' ';	
	return 0;
}