#include <fstream>
#include <vector>
#define INF 999999999

using namespace std;

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

struct muchie
{
	int x, c;
};

struct drum
{
	int c, nr;
};

void push(drum d);
void update(int poz, int c);
drum popMin();

int n, m, nH, poz[50005], sol[50005];
vector<muchie> L[50005];
drum H[50005];

int main()
{
	int i, x, y, c;
	muchie aux;
	drum auxx;

	fin >> n >> m;
	for (i = 1; i <= m; i++)
	{
		fin >> x >> aux.x >> aux.c;
		L[x].push_back(aux);
	}
	for (i = 0; i<L[1].size(); i++)
	{
		auxx.c = L[1][i].c;
		auxx.nr = L[1][i].x;
		push(auxx);
	}
	for (i = 2; i <= n; i++)
		if (!poz[i])
		{
			auxx.c = INF;
			auxx.nr = i;
			push(auxx);
		}
	while (nH)
	{
		auxx = popMin();
		sol[auxx.nr] = auxx.c;
		for (i = 0; i<L[auxx.nr].size(); i++)
		{
			y = L[auxx.nr][i].x;
			c = L[auxx.nr][i].c;
			if (H[poz[y]].c > auxx.c + c)
				update(poz[y], auxx.c + c);
		}
	}
	for (i = 2; i <= n; i++)
	{
		if (sol[i] != INF)
			fout << sol[i] << ' ';
		else fout << 0 << ' ';
	}
	fout << '\n';
	return 0;
}

void push(drum d)
{
	int fiu, tata;

	fiu = ++nH;
	tata = fiu / 2;
	while (d.c < H[tata].c && tata)
	{
		poz[H[tata].nr] = fiu;
		H[fiu] = H[tata];
		fiu = tata;
		tata = fiu / 2;
	}
	H[fiu] = d;
	poz[d.nr] = fiu;
}

void update(int pozz, int c)
{
	int fiu, tata;
	drum aux;

	aux = H[pozz];
	aux.c = c;
	fiu = pozz;
	tata = fiu / 2;
	while (aux.c < H[tata].c && tata)
	{
		poz[H[tata].nr] = fiu;
		H[fiu] = H[tata];
		fiu = tata;
		tata = fiu / 2;
	}
	H[fiu] = aux;
	poz[aux.nr] = fiu;
}

drum popMin()
{
	int fiu, tata;
	drum rez = H[1], aux;

	H[1] = H[nH--];
	aux = H[1];
	tata = 1;
	while (1)
	{
		fiu = 2 * tata;
		if (fiu > nH)
			break;
		if (H[fiu].c > H[fiu + 1].c && fiu<nH)
			fiu++;
		if (aux.c < H[fiu].c)
			break;
		H[tata] = H[fiu];
		poz[H[tata].nr] = tata;
		tata = fiu;
	}
	H[tata] = aux;
	poz[aux.nr] = tata;
	return rez;
}