#include <iostream>
#include <cstdlib>
#include <fstream>
#include <limits>
#include <map>

using namespace std;
ifstream f("dijkstra.in" );
ofstream g("dijkstra.out");

#define MAXN 50005
#define MAXM 50005

#define START 1


bool done[MAXN];
int  MinDist[MAXN], N, M;

map< int, int > Adiacenta[MAXN];

int main()
{
	f >> N >> M;

	for ( int i=1; i<=M; i++)
	{
		int x, y, z;

		f >> x >> y >> z;

		Adiacenta[x][y] = z;
	}

	for ( int i=1; i<=N; i++ )
		if ( Adiacenta[START].count(i) > 0 )
			MinDist[i] = Adiacenta[START][i];
		else
			MinDist[i] = numeric_limits<int>::max();

	MinDist[START] = 0;
	done[START] = true;

	for ( int i=1; i<=N-1; i++ )
	{
		int BestVal = numeric_limits<int>::max();
		int BestInd = 0;

		for ( int j=1; j<=N; j++ )
			if ( !done[j] && MinDist[j] < BestVal )
			{
				BestVal = MinDist[j];
				BestInd = j;
			}

		done[BestInd] = true;

		for ( int j=1; j<=N; j++ )
			if ( Adiacenta[BestInd].count(j) > 0 )
			{
				int segment = Adiacenta[BestInd][j];
				if ( BestVal + segment < MinDist[j] )
					MinDist[j] = BestVal + segment;
			}
	}

	for ( int i=2; i<=N; i++ )
		g << (MinDist[i]==numeric_limits<int>::max()?0:MinDist[i]) << ' ';
}