#include <iostream>
#include <fstream>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <bitset>

using namespace std;


struct Order
{
	bool operator()( const pair< int, int > &firstElem, const pair< int, int > &secondElem )
	{
		return firstElem.second > secondElem.second;
	}
};

int main()
{
	// N noduri M arce
	int N, M;
	
	vector< vector< pair< int, int > > > g(50001);

	unsigned int dist[50001]; // distanta minima de la nodu 1 la nodul i

	//memset( dist, 0xFF, sizeof( dist ) );
	

	ifstream fin( "dijkstra.in" );
	fin >> N >> M;

	

	int A, B, C;
	priority_queue< pair< int, int >, vector< pair <int, int > >, Order > Q;
	for (int i = 0; i < M; ++i)
	{		
		fin >> A >> B >> C;
		
		g[A].push_back( { B, C } );
	}
	fin.close();

	memset( dist, 0xFF, sizeof( dist ) );
	
	int u, best_cost;

	Q.push( { 1, 0 } );
	dist[1] = 0; //dist de la sursa la sursa

	while (!Q.empty())
	{
		u = Q.top().first;
		best_cost = Q.top().second;
		Q.pop();

		for (unsigned int i = 0; i < g[u].size(); ++i)
		{
			B = g[u][i].first;
			C = g[u][i].second;

			if (dist[B] > best_cost + C )
			{
				dist[B] = best_cost + C;
				Q.push( { B, dist[B] } );
			}

		}
	}

	ofstream fout( "dijkstra.out" );
	for (int i = 2; i <= N; ++i)
	{
		fout << dist[i] << " ";
	}
	fout.close();
	
    return 0;
}