#include <queue>
#include <vector>
#include <algorithm>
#include <fstream>
#include <functional>

using namespace std;
const int NMAX = 50003;
const int INF = 0x3f3f3f3f;

int N, M;

int d[NMAX];

typedef pair<int, int> ii;
vector<ii> g[NMAX];

void Dijkstra(int nod)
{
	fill(d, d + N + 1, INF);

	priority_queue<ii, vector<ii>, greater<ii> > Q;

	d[nod] = 0;
	Q.push(ii(0, nod));

	while (!Q.empty())
	{
		ii it = Q.top();
		Q.pop();

		int dist = it.first;
		nod = it.second;

		if (dist <= d[nod])
		{
			for (auto &x : g[nod])
			{
				int cost = x.second;
				int v = x.first;
				if (d[nod] + cost < d[v])
				{
					d[v] = d[nod] + cost;
					Q.push(ii(d[v], v));
				}
			}			
		}
	}
}

int main(){
	ifstream cin("dijkstra.in");
	ofstream cout("dijkstra.out");

	cin >> N >> M;

	int x, y, c;
	for (int i = 0; i < M; ++i)
	{
		cin >> x >> y >> c;
		g[x].push_back(ii(y, c));
	}

	Dijkstra(1);

	for (int i = 2; i <= N; ++i)
		cout << d[i] << ' ';

	cin.close();
	cout.close();

	return 0;
}