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

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

int n, m, d[MAXN], stop, p[MAXN];
vector <pair <int, int>> list[MAXN];

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

void dijkstra()
{
	while (!stop)
	{
		int min = inf, pos;
		for (int i = 1; i <= n; i++)
			if (d[i] < min && !p[i])
				min = d[i],
				pos = i;
		if (min != inf)
		{
			p[pos] = 1;
			for (int i = 0; i < list[pos].size(); i++)
				if (d[list[pos][i].first] > d[pos] + list[pos][i].second)
					d[list[pos][i].first] = d[pos] + list[pos][i].second;
		}
		else stop = 1;
	}
}

int main() 
{
	read();
	for (int i = 2; i <= n; i++)
		d[i] = inf;
	dijkstra();

	for (int i = 2; i <= n; i++)
		if (d[i] == inf)	fout << 0 << ' ';
		else fout << d[i] << ' ';

	fout.close();
	return 0;
}