#include<stdio.h>
#include<set>
#include<vector>
using namespace std;

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

int main()
{
	int u, v, c, i, j, ind = 0, m[50001], minim;
	
	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.insert( make_pair(0, 1) );
	for(i = 2; i <= N; i++)
	{
		D[i] = inf;
		heap.insert( make_pair(D[i], i) );
	}
	
	// dijkstra

	for(i = 1; i <= N-1; i++)
	{
		pair<int, int> p = *heap.begin();
		ind = p.second;
		heap.erase(heap.begin()); // sterge radacina
					
		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])
			{
				heap.erase(heap.find( make_pair(D[v], v) ));				
				D[v] = D[ind] + c; // relaxare
				heap.insert( make_pair(D[v], v) );
			}
		}
	}
	
	for (i = 2; i <= N; i++)
		if (D[i] == inf)
			printf("0 ");
		else
			printf("%d ", D[i]);
	printf("\n");
	
	return 0;
}