#include <algorithm>
#include <climits>
#include <fstream>
#include <iterator>
#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, INT_MAX);
	set<pair<int, int> > s;

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

	while (!s.empty())
	{
		int z = s.begin()->first;
		int x = s.begin()->second;
		s.erase(s.begin());

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

	ofstream out("dijkstra.out");
	copy(d.begin() + 2, d.end(), ostream_iterator<int>(out, " "));
}