#include <fstream>
#include <vector>
//#include <stack>

using namespace std;
#define MAXN 50000
#define inf 2147483647
fstream fout("dijkstra.out", ios::out);

int n, m, d[MAXN], stop;
vector <int> list[MAXN], cost[MAXN];
unsigned long int p[1600];

inline void read()
{
	int x, y, c;
	fstream fin("dijkstra.in", ios::in);
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
		fin >> x >> y >> c,
		list[x].push_back(y),
		cost[x].push_back(c);
	fin.close();
}

void dijkstra()
{
	int min = inf, pos;
	for (int i = 1; i <= n; i++)
		if (!(p[i / 32] & (1 << (i - 1) % 32)) && d[i] < min)
			min = d[i],
			pos = i;
	if (min != inf)
	{
		p[pos / 32] = p[pos / 32] | 1 << (pos - 1) % 32;
		for (int i = 0; i < list[pos].size(); i++)
			if (d[list[pos][i]] > d[pos] + cost[pos][i])
				d[list[pos][i]] = d[pos] + cost[pos][i];
	}
	else stop = 1;
}

int main() 
{
	read();
	for (int i = 2; i <= n; i++)
		d[i] = inf;
	while (!stop)
		dijkstra();
	for (int i = 2; i <= n; i++)
		fout << d[i] << " ";

	fout.close();
	return 0;
}