#include <cstdio>
#include <iostream>
#define DIM 50005
#define INF 100000001
using namespace std;

void Read();
void Add(int x, int y, int z);
void Dijkstra(int S);
void Insert(int nod);
int ExtractMin();
void RebuildHeap(int key);
void MoveUp(int nod);
void Write();

int H[DIM], P[DIM], D[DIM], sel[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 = 1; i <= N; i++)
		D[i] = INF;
	D[S] = 0;
	sel[S] = 1;
	for (PNOD p = L[S]; p; p = p->next)
	{
		D[p->vf] = p->c;
		sel[p->vf] = 1;
		Insert(p->vf);
	}
	while (dh)
	{
		int i = ExtractMin();
		sel[i] = 0;
		for (PNOD p = L[i]; p; p = p->next)
			if (D[p->vf] > D[i] + p->c)
			{
				D[p->vf] = D[i] + p->c;
				if (!sel[p->vf])
				{
					sel[p->vf] = 1;
					Insert(p->vf);
				}
				else
					MoveUp(p->vf);
			}
	}
}

void Insert(int nod)
{
	dh++;
	int S = dh, T = dh / 2;
	while (S > 1 && D[H[T]] > D[nod])
	{
		H[S] = H[T];
		P[H[S]] = S;
		S = T;
		T = S / 2;
	}
	H[S] = nod;
	P[nod] = S;
}

int ExtractMin()
{
	int sol = H[1];
	H[1] = H[dh];
	P[H[1]] = 1;
	dh--;
	RebuildHeap(1);
	return sol;
}

void RebuildHeap(int key)
{
	int T = key, S = 2 * key;
	while (S <= dh)
	{
		if (S < dh && D[H[S]] < D[H[S + 1]]) S++;
		if (D[H[key]] < D[H[S]])
		{
			int aux = H[T];
			H[T] = H[S];
			H[T] = aux;
			P[H[T]] = T;
			T = S;
			S *= 2;
		}
		else
		{
			H[T] = H[key];
			P[H[key]] = T;
			return;
		}
	}
	H[T] = H[key];
	P[H[key]] = T;
}

void MoveUp(int nod)
{
	int S = P[nod];
	int T = S / 2;
	while (T && D[H[T]] > D[nod])
	{
		H[T] = H[S];
		P[H[T]] = S;
		S = T;
		T /= 2;
	}
	H[S] = nod;
	P[nod] = S;
}

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);
}