/* Aplicatie la Priority Queue: Dijkstra - O(M*logN) */

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;

#define NMAX 100000
#define INF 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define nod first
#define cost second
#define VPII vector< pair< int, int > >

int 	N, M, x, y, c, i;
int	Dist[NMAX];
VPII	G[NMAX];

struct comp
{
	bool operator() (const int &X, const int &Y)
	{
		return ( Dist[X] > Dist[Y] ); // functia de comparare pentru priority_queue
							    // (returneaza true daca trebuie facut swap in interiorul cozii care functioneaza ca un min-heap)
	}
};

priority_queue< int, vector< int >, comp > Q;

inline void Dijkstra( int Sursa )
{
	memset( Dist, INF, NMAX ); //initial toate distantele sunt infinit
	Dist[Sursa] = 0; //in afara de distanta pana la sursa

	Q.push( Sursa );

	while( !Q.empty() )
	{
		int Nod = Q.top(); //se va selecta succesiv cel mai ''apropiat'' nod de sursa - cel cu distanta minima
		Q.pop();

		for( VPII::iterator it = G[Nod].begin(); it != G[Nod].end(); ++it )
			if( Dist[ (*it).nod ] > Dist[Nod] + (*it).cost )
			{
				Dist[ (*it).nod ] = Dist[Nod] + (*it).cost;
				Q.push( (*it).nod );
			}
	}
}

int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	scanf("%d%d%d", &N, &M);
	for( ; M--; )
	{
		scanf("%d%d%d", &x, &y, &c ); // muchia curenta x <-> y cu costul c
		G[x].pb( mp( y, c ) );
		//G[y].pb( mp( x, c ) );
	}
	Dijkstra( 1 );

	for( i = 2; i <= N; ++i )
		printf("%d ", Dist[i] ); // distantele de la nodul sursa (1) la toate celelalte

	return 0;
}