#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
#include <list>

#define INF 66613
#define NIL -1

struct Node {

	int _node;
	int _cost;

	Node( int node, int cost ): _node(node), _cost(cost) {}
};

class Graph {

private:
	std::vector<Node> * _adj_list;
	int _size;
public:

	Graph( int N ): _size(N) {

		_adj_list = new std::vector<Node>[N * 2];
	}
	~Graph() {

		delete[] _adj_list;
	}

	void add_edge( const int u, const int v, const int d ) {
		_adj_list[u].push_back( Node(v, d) );
	}

	void printArr(const std::vector<int> dist, int n) {

	    printf("Vertex   Distance from Source\n");
	    for (int i = 1; i <= n; ++i)
	        printf("%d \t\t %d\n", i, dist[i]);
	}

	std::pair< std::vector<int> ,std::vector<int>> Dijkstra( const int &src ) {

		std::vector<int> min_distance( _size + 1, INF );
		std::vector<int> previous( _size + 1, NIL );
		std::set< std::pair<int,int>> pq;

		min_distance[src] = 0;
	
		pq.insert( std::make_pair( src, min_distance[src] ) );

		while ( !pq.empty() ) {

			int node = pq.begin()->first;
			int cost = pq.begin()->second;

			pq.erase( pq.begin() );

			for ( auto it = _adj_list[node].begin(); it != _adj_list[node].end(); ++it ) {

				int u_vertex = it->_node;
				int u_weight = it->_cost;
				int computed_distance = cost + u_weight;
				//std::cout << computed_distance << " vs. " << min_distance[u_vertex] << std::endl;
				if ( computed_distance < min_distance[u_vertex] ) {

					pq.erase ( std::make_pair( u_vertex, min_distance[u_vertex] ) );

					min_distance[u_vertex] = computed_distance;
					previous[u_vertex] = node;

					pq.insert ( std::make_pair( u_vertex, min_distance[u_vertex]) );					
				}
			}
		}

		printArr( min_distance, _size );

		return std::make_pair( previous, min_distance );
	}

};



int main(int argc, char const *argv[])
{
	FILE *f_in, *f_out;
	
	f_in = fopen ( "grader_test1.in", "r" );
	f_out = fopen ( "dijkstra.out", "w" );

	if ( !f_in ) {
		perror ( "can't open file!");
		return -1;
	}


	int N, M;

	fscanf( f_in, "%d %d", &N, &M);

	int u, v, d;
	Graph g(N);

	for ( int i = 0; i < M; ++i ) {
		
		fscanf(f_in, "%d %d %d", &u, &v, &d);
		g.add_edge( u, v, d );
	}

	std::pair< std::vector<int> ,std::vector<int>> tmp = g.Dijkstra( 1 );

	std::vector<int> prev = tmp.first;
	std::vector<int> dist = tmp.second;

	for ( int i = 2; i < (int)dist.size(); ++i ) {
		std::cout << dist[i] << ' ';
		fprintf( f_out, "%d ", dist[i]);
	}

	std::cout << std::endl;

	fclose( f_out );
	fclose( f_in );

	return 0;
}