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

using namespace std;

typedef pair< int, int > pereche;

struct Order
{
	bool operator()( const pereche &firstElem, const pereche &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;

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

	priority_queue< pair< int, int > > Q;
	int u;

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

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

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

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

		}
	}

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