#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 1e9
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N, M, d[50005];
bool viz[50005];
vector <pair<int, int>>v[50005];
priority_queue<pair<int, int>>P;
void Relaxare(int nod)
{
	//cout << "AAA\n";
	viz[nod] = 1;
	for (int i = 0; i < v[nod].size(); i++)
	{
		if (v[nod][i].first + d[nod] < d[v[nod][i].second]) {P.push(make_pair(v[nod][i].first + d[nod], v[nod][i].second));
															 d[v[nod][i].second] = v[nod][i].first + d[nod];
															}
	}
}
int main()
{
	int x, y, z, N, M;
	fin >> N >> M;
	for (int i = 0; i < M; i++)
	{
		fin >> x >> y >> z;
		v[x].push_back(make_pair(-z, y));
	}

	P.push(make_pair(1, 0));
	for (int i = 2; i <= N; i++)
	{
		d[i] = inf;
		P.push(make_pair(inf, i));
	}
	for (int i = 0; i < v[1].size(); i++)
		d[v[1][i].second] = v[1][i].first;
	while (!P.empty())
	{
		if (viz[P.top().second] == 0)
			Relaxare(P.top().second);
		else P.pop();
	}
	for (int i = 2; i <= N; i++)
		fout << -d[i] << " ";
}