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

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct edge
{
	int x, cost;
	friend bool operator > (edge a, edge b)
	{
		return a.cost > b.cost;
	}
};

void citire();
void dijkstra();
void afisare();

const int INF = 1e9 + 1;
int n, m;
bool uz[50005];
priority_queue<edge, vector<edge>, greater<edge> > H;
vector<int> M;
vector<edge> G[50005];
int d[50005];

int main()
{
	citire();
	dijkstra();
	afisare();
	return 0;
}

void afisare()
{
	for (int i = 2; i <= n; i++)
		fout << (d[i] == INF ? 0 : d[i]) << ' ';
	fout << '\n';
}

void dijkstra()
{
	H.push({ 1, 0 });
	while (M.size() < n && !H.empty() && H.top().cost != INF)
	{
		edge e = H.top(); H.pop();
		if (uz[e.x] && e.x != 1) continue;

		uz[e.x] = true;
		M.push_back(e.x);

		for (unsigned i = 0; i < G[e.x].size(); i++)
		{
			int y = G[e.x][i].x;
			int cost = G[e.x][i].cost;
			if (!uz[y] && d[e.x] + cost < d[y])
			{
				d[y] = d[e.x] + cost;
				H.push({ y, d[y] });
			}
		}
	}
}

void citire()
{
	fin >> n >> m;
	int x, y, cost;

	for (int i = 2; i <= n; i++)
		d[i] = INF;

	for (int i = 1; i <= m; i++)
	{
		fin >> x >> y >> cost;
		G[x].push_back({ y, cost });
		if (x == 1)
		{
			d[y] = cost;
			H.push({ y, cost });
		}
	}
}