#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

vector <pair <int, int>> v[50001];
long long d[50001];

struct el
{
	long long c;
	int nod;
	bool operator <(const el&alt) const
	{
		return c > alt.c;
	}
};

priority_queue<el> p;

bool b[50001];

int main()
{
	int n, m, i, j, x, y, z;
	el bun;
	fin >> n >> m;
	for (i = 1; i<=m; i++)
	{
		fin >> x >> y >> z;
		v[x].push_back({y, z});
	}
	for (i = 1; i<=n; i++)
		d[i] = 1ll<<50;
	d[1] = 0;
	p.push({0, 1});
	for (i = 1; i<=n; i++)
	{
		while (p.empty() == 0 && b[p.top().nod])
			p.pop();
		if (p.empty())
			break;
		
		bun = p.top();
		b[bun.nod] = 1;
		p.pop();
		for (j = 0; j<v[bun.nod].size(); j++)
			if (d[v[bun.nod][j].first] > bun.c + v[bun.nod][j].second)
			{
				d[v[bun.nod][j].first] = bun.c + v[bun.nod][j].second;
				p.push({d[v[bun.nod][j].first], v[bun.nod][j].first});
			}
	}
	for (i = 2; i<=n; i++)
	{
		if (d[i] == (1ll<<50))
			fout << "0 ";
		else
			fout << d[i] << ' ';
	}
    return 0;
}