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

#define BYTE_INF std::numeric_limits<char>::max() 
#define INF 	 std::numeric_limits<int >::max()
#define MAXN 	 50005
#define MAXM 	 50005
#define START 	 1

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

unsigned int MinDist[MAXN], N, M;

std::map< int, int > Adiacenta[MAXN];
std::set< std::pair<int, int> > partial;

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

	for ( int i=1, x, y, z; i<=M; i++)
	{
		f >> x >> y >> z;
		Adiacenta[x][y] = z;
	}

	memset(MinDist, BYTE_INF, sizeof(MinDist));
	MinDist[START] = 0;
	partial.insert( std::make_pair(0, 1) );

	while ( !partial.empty() )
	{
		int distance = partial.begin()->first;
		int node     = partial.begin()->second;
		partial.erase(partial.begin());

		for ( std::map<int, int>::iterator it = Adiacenta[node].begin(); it!=Adiacenta[node].end(); ++it )
		{
			int target  = it->first;
			int segment = it->second;

			if ( distance + segment < MinDist[target] )
			{
				if ( MinDist[target] != INF )
					partial.erase( std::make_pair(MinDist[target], target) );

				MinDist[target] = distance + segment;
				partial.insert( std::make_pair(MinDist[target], target) );
			}
		}
	}



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