#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int N, M;

#define N_MAX 50001
#define M_MAX 250001
#define E_MAX_LENGTH 20001
#define inf 1000000001

typedef struct graphMatrix {
	int** costMatrix;
	int numNodes;
} graphMatrix;

typedef struct nodeNDP {
	int node;
	int d;
	int parent;
	int visited;
} nodeNDP;

graphMatrix readFile( const char* filename )
{
	graphMatrix graph;
	FILE* f = fopen( filename, "r" );
	if ( f == NULL ) {
		printf( "ERROR AT OPENING FILE %s \n", filename );
		return graph;
	}
	fscanf( f, "%d %d", &N, &M );
	graph.numNodes = N;
	graph.costMatrix = (int**)malloc( sizeof( int* ) * ( graph.numNodes + 1 ) );
	for ( int i = 0; i < graph.numNodes; i++ ) {
		graph.costMatrix[i] = (int*)malloc( sizeof( int ) * ( graph.numNodes + 1 ) );
		for ( int j = 0; j < graph.numNodes; j++ ) {
			if ( i == j ) {
				graph.costMatrix[i][j] = 0;
				continue;
			}
			graph.costMatrix[i][j] = inf;
		}
	}

	int A, B, C;
	for ( int i = 0; i < M; i++ ) {
		fscanf( f, "%d %d %d", &A, &B, &C );
		graph.costMatrix[A - 1][B - 1] = C;
	}

	fclose( f );

	return graph;
}

nodeNDP* dijkstra( graphMatrix graph, int source )
{
	nodeNDP* NDP = (nodeNDP*)malloc( sizeof( nodeNDP ) * ( N + 1 ) );
	for ( int i = 1; i <= N; i++ ) {
		NDP[i].node = i;
		NDP[i].d = inf;
		NDP[i].parent = -1;
		NDP[i].visited = 0;
	}
	source--;
	NDP[source].d = 0;
	int count = 1;
	int min = 0;

	while ( count <= graph.numNodes - 1 ) {
		for ( int i = 0; i < graph.numNodes; i++ ) {
			if ( source != i && graph.costMatrix[source][i] != inf && NDP[i].visited == 0 ) {
				int distance = NDP[source].d + graph.costMatrix[source][i];
				if ( distance < NDP[i].d ) {
					NDP[i].d = distance;
					NDP[i].parent = source;
				}
			}
		}
		NDP[source].visited = 1;
		count++;
		min = inf;
		for ( int i = 1; i <= graph.numNodes; i++ ) {
			if ( min > NDP[i].d && NDP[i].visited == 0 ) {
				min = NDP[i].d;
				source = i;
			}
		}
	}

	return NDP;
}

int main()
{
	graphMatrix graph = readFile( "dijkstra.in" );

	nodeNDP* NDP = dijkstra( graph, 1 );

	FILE* f = fopen( "dijkstra.out", "w" );
	for ( int i = 1; i < N; i++ ) {
		if ( NDP[i].d == inf ) {
			fprintf( f, "%d ", 0 );
		} else {
			fprintf( f, "%d ", NDP[i].d );
		}
	}
	fclose( f );

	return 0;
}