#include <algorithm>
#include <bitset>
#include <fstream>
#include <iterator>
#include <queue>
#include <vector>
#include <utility>
using namespace std;

vector<int> d;

struct comp
{
	bool operator ()(int x, int y)
	{
		return d[x] > d[y];
	}
};

int main()
{
	ifstream in("dijkstra.in");
	
	int N, M;
	in >> N >> M;
	
	vector<vector<pair<int, int> > > g(N + 1);
	d.resize(N + 1, INT_MAX);
	d[1] = 0;

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

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

	bitset<50001> is;
	queue<int> q;

	for (q.push(1); !q.empty(); q.pop())
	{
		int x = q.front();
		is[x] = false;

		for (int i = 0; i < static_cast<int>(g[x].size()); i++)
		{
			int y = g[x][i].first;
			int z = g[x][i].second;

			if (d[y] > d[x] + z)
			{
				d[y] = d[x] + z;

				if (!is[y])
				{
					q.push(y);

					is[y] = true;
				}
			}
		}
	}
	
	ofstream out("dijkstra.out");
	copy(d.begin() + 2, d.end(), ostream_iterator<int>(out, " "));
}