#include <fstream>
#include <limits>
#include <set>
#include <vector>
#include <utility>
using namespace std;

int main()
{
	ifstream in("dijkstra.in");

	int N, M;
	in >> N >> M;
	
	vector<vector<int> > a(M);
	vector<vector<int> > g(M);

	for (int i = 1; i <= M; i++)
	{
		int x, y, z;
		in >> x >> y >> z;

		g[x].push_back(y);
		a[x].push_back(z);
	}

	vector<int> d(N + 1, numeric_limits<int>::max());
	set<pair<int, int> > t;

	t.insert(make_pair(0, 1));

	while (t.size() > 0)
	{
		int val = (*t.begin()).first;
		int x = (*t.begin()).second;
		t.erase(*t.begin());

		for (int i = 0; i < static_cast<int>(g[x].size()); i++)
		{
			if (d.at(g[x][i]) > val + a[x][i])
			{
				d.at(g[x][i]) = val + a[x][i];
				
				t.insert(make_pair(d.at(g[x][i]), g[x][i]));
			}
		}
	}

	ofstream out("dijkstra.out");
	for (int i = 2; i <= N; i++)
		out << ((d[i] == INT_MAX) ? 0 : d[i]) << ' ';
}