#include <bits/stdc++.h>
#define Dim 50001
#define oo 1e9+1
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int D[Dim], x, y, z, N, M;

typedef pair<int, int> pi;
vector < pi > V[Dim];

struct cmp
{
	bool operator ()(int x, int y)
	{
		if (D[x] < D[y]) return 1;
		else
			if (D[x] == D[y])
			{
				if (x < y) return 1;
				else return 0;
			}
			else return 0;
	}
};

set < int, cmp > S;
set < int, cmp > ::iterator it, it_find;


void Dikstra()
{
	D[1] = 0;
	S.insert(1);

	while (!S.empty())
	{
		int nod = *S.begin();
		S.erase(S.begin());

		for (unsigned int i = 0; i < V[nod].size(); i++)
		{
			int vecin = V[nod][i].first;
			int cost = V[nod][i].second;
			if (D[vecin] > D[nod] + cost)
			{
				if (D[vecin] != oo) S.erase(S.find(vecin));
				D[vecin] = D[nod] + cost;
				S.insert(vecin);
			}
		}
	}
}

int main()
{
	in >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		in >> x >> y >> z;
		V[x].push_back({ y,z });
	}
	for (int i = 1; i <= N; i++) D[i] = oo;
	Dikstra();

	for (int i = 2; i <= N; i++)
		if (D[i] == oo) out << 0 << " ";
		else out << D[i] << " ";

	return 0;
}