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

using namespace std;

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

const int NMAX = 50005;
const int INF = 2e9;

struct edge {
	int y, cost;
	bool operator<(const edge& other) const {
		return cost > other.cost;
	}
};

priority_queue<edge>pq;
vector<edge>G[NMAX];

int distMin[NMAX];
bool viz[NMAX];

int m, n;

void dijkstra()
{
	for (int i = 1; i <= n; i++)
		distMin[i] = INF;
	
	pq.push(edge({ 1,0 }));

	while (!pq.empty())
	{
		edge u = pq.top();
		pq.pop();

		if (distMin[u.y] != INF) continue;

		distMin[u.y] = u.cost;

		for (edge v : G[u.y])
			pq.push(edge({v.y, v.cost+u.cost}));
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0); fout.tie(0);
	fin >> n >> m;
	while (m--)
	{
		int a, b, c;
		fin >> a >> b >> c;
		G[a].push_back(edge({ b,c }));
	}
	dijkstra();
	for (int i = 2; i <= n; i++)
		fout << ((distMin[i] == INF) ? 0 : distMin[i]) << ' ';
	fout << '\n';
	return 0;
}