#include <fstream>
#include <vector>
#include <set>
#define inf 1e9
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector <pair<int, int>> v[50005];
int d[50005], f[50005], N, M;
set<pair<int, int>>S;
pair<int, int> a;
void Relaxare(int nod)
{
	int i, mn = inf, p = 0;
	S.erase(make_pair(d[nod], nod));
	for (i = 0; i < v[nod].size(); i++)
		if (d[v[nod][i].first] > v[nod][i].second + d[nod])
		{
			S.erase(make_pair(d[v[nod][i].first], v[nod][i].first));
			d[v[nod][i].first] = v[nod][i].second + d[nod];
			S.insert(make_pair(d[v[nod][i].first], v[nod][i].first));
		}
	if (!S.empty())
		Relaxare((*S.begin()).second);
}
int main()
{
	int i, x, y, z;
	fin >> N >> M;
	for (i = 1; i <= M; i++)
	{
		fin >> x >> y >> z;
		a.first = y;
		a.second = z;
		v[x].push_back(a);
	}
	d[1] = 0;
	for (i = 2; i <= N; i++)
	{
		d[i] = inf;
	}
	Relaxare(1);
	for (i = 2; i <= N; i++)
	{
		if (d[i] != inf)
			fout << d[i] << " ";
		else
			fout << "0 ";
	}
}