#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, sol[50005], uz[50005];
vector<muchie> L[50005];
drum H[500005];

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

	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);
		sol[L[1][i].x] = L[1][i].c;
	}
	for (i = 2; i <= n; i++)
		if (!sol[i])
			sol[i] = INF;
	for (j = 2; j <= n; j++)
	{
		if (!nH)
			break;
		do
		{
			auxx = popMin();
		} while (uz[auxx.nr] && nH);
		uz[auxx.nr] = 1;
		for (i = 0; i<L[auxx.nr].size(); i++)
		{
			y = L[auxx.nr][i].x;
			c = L[auxx.nr][i].c;
			if (sol[y] > auxx.c + c)
			{
				//update(poz[y],auxx.c+c);
				aux2.c = auxx.c + c;
				aux2.nr = y;
				sol[y] = aux2.c;
				push(aux2);
			}
		}
	}
	for (i = 2; i <= n; i++)
	{
		if (sol[i] == INF)
			fout << 0 << ' ';
		else fout << sol[i] << ' ';
	}
	fout << '\n';
	return 0;
}

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

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

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)
	{
		H[fiu] = H[tata];
		fiu = tata;
		tata = fiu / 2;
	}
	H[fiu] = aux;
}

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+1<=nH)
			fiu++;
		if (aux.c <= H[fiu].c)
			break;
		H[tata] = H[fiu];
		tata = fiu;
	}
	H[tata] = aux;
	return rez;
}