#include <cstdio>
#include <iostream>
#define DIM 50005
#define INF (1 << 30)
using namespace std;

void Read();
void Add(int x, int y, int z);
void Dijkstra(int S);
int ExtractMin();
void MoveUp(int key);
void MoveDown(int key);
void Swap(int x, int y);
void Write();

int H[DIM], P[DIM], D[DIM];
int N, M, dh;
typedef struct Nod {
	int vf, c;
	Nod* next;
} NOD, *PNOD;
PNOD L[DIM];

int main()
{
	Read();
	Dijkstra(1);
	Write();
	return 0;
}

void Read()
{
	FILE *fin = fopen("dijkstra.in", "r");
	fscanf(fin, "%d%d", &N, &M);
	int x, y, c;
	for (int i = 1; i <= M; i++)
	{
		fscanf(fin, "%d%d%d", &x, &y, &c);
		Add(x, y, c);
	}
	fclose(fin);
}

void Add(int x, int y, int z)
{
	PNOD p = new NOD;
	p->vf = y;
	p->c = z;
	p->next = L[x];
	L[x] = p;
}

void Dijkstra(int S)
{
	for (int i = 2; i <= N; i++)
	{
		D[i] = INF;
		dh++;
		H[dh] = i;
		P[i] = dh;
	}
	for (PNOD p = L[S]; p; p = p->next)
	{
		D[p->vf] = p->c;
		MoveUp(P[p->vf]);
	}
	while (dh)
	{
		int i = ExtractMin();
		for (PNOD p = L[i]; p; p = p->next)
			if (D[p->vf] > D[i] + p->c)
			{
				D[p->vf] = D[i] + p->c;
				MoveUp(P[p->vf]);
			}
	}
}

int ExtractMin()
{
	int minim = H[1];
	Swap(1, dh);
	P[H[dh]] = 0;
	dh--;
	MoveDown(1);
	return minim;
}

void MoveUp(int key)
{
	if (key == 1) return;
	int T = key / 2;
	if (D[H[T]] > D[H[key]])
	{
		Swap(T, key);
		MoveUp(T);
	}
}

void MoveDown(int key)
{
	int F = 2 * key;
	if (F > dh) return;
	if (F < dh && D[H[F]] > D[H[F + 1]]) F++;
	if (D[H[F]] < D[H[key]])
	{
		Swap(F, key);
		MoveDown(F);
	}
}

void Swap(int x, int y)
{
	int aux = H[x];
	H[x] = H[y];
	H[y] = aux;
	P[H[x]] = x;
	P[H[y]] = y;
}

void Write()
{
	FILE *fout = fopen("dijkstra.out", "w");
	for (int i = 2; i <= N; i++)
		if (D[i] != INF) fprintf(fout, "%d ", D[i]);
		else             fprintf(fout, "0 ");
	fclose(fout);
}