#include<stdio.h>
#include<set>
#include<vector>

using namespace std;

typedef struct { int nod, d; } heap_node;

int N, M;
vector< pair<int, int> > G[50035];
int D[50001];
const int inf = 999999999;
heap_node heap[50001]; int nr;
int poz[50001];

// urcare
void percolate(int n)
{
	while (n > 1 && heap[n].d <= heap[n/2].d)
	{
		heap_node aux = heap[n];
		heap[n] = heap[n/2];
		heap[n/2] = aux;
		
		poz[heap[n].nod] = n;
		poz[heap[n/2].nod] = n/2;
				
		n = n / 2;
	}
}

// coborare
void sift(int n)
{
	while (n * 2 <= nr) // are cel putin fiu stanga, nu e frunza
	{
		int i = n * 2;
		if (n * 2 + 1 <= nr && heap[n * 2 + 1].d < heap[n * 2].d)
			i = n * 2 + 1;
		
		if (heap[i].d >= heap[n].d)
			return ;
		
		// interschimb nodul n cu nodul i
		heap_node aux = heap[n];
		heap[n] = heap[i];
		heap[i] = aux;
		
		poz[heap[n].nod] = n;
		poz[heap[i].nod] = i;
		
		n = i;
	}
}

int main()
{
	int u, v, c, i, j, ind = 0;
	
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	
	scanf("%d%d", &N, &M);
	for(i = 1; i <= M; i++)
	{
		scanf("%d %d %d", &u, &v, &c); // u->v cost c
		G[u].push_back( make_pair(v, c) );
	}

	heap[1].nod = 1; heap[1].d = 0;
	for(i = 2; i <= N; i++)
	{
		heap[i].nod = i;
		heap[i].d = inf;
		D[i] = inf;
	}
	nr = N;
	for (i = 1; i <= N; i++)
		poz[i] = i;
	
	// dijkstra cu heap-uri
	for(i = 1; i <= N-1; i++)
	{
		heap_node radacina = heap[1];
		
		// stergem radacina
		heap[1] = heap[nr];
		poz[heap[nr].nod] = 1;
		nr--;
		sift(1); // coborare daca este nevoie
		
		// actualizam nodurile vecine
		ind = radacina.nod;
		int nr_v = G[ind].size();
		for (j = 0; j < nr_v; j++)
		{
			int v = G[ind][j].first;
			int c = G[ind][j].second;
			if (D[ind] + c < D[v])
			{
				D[v] = D[ind] + c; // relaxare
				
				// poz[v] - nodul din heap unde se gaseste nodul v din graf
				heap[poz[v]].d = D[v];
				percolate(poz[v]);
			}
		}
	}
	
	for (i = 2; i <= N; i++)
		if (D[i] == inf)
			printf("0 ");
		else
			printf("%d ", D[i]);
	printf("\n");
	
	return 0;
}