#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

void do_nothing(int a)
{


}

int get_minimum_unvisited(bool*visited,int number_of_nodes,int *distances,int node)
{
	int minimum=10000;
	int index=-1;

	for(int i=0;i<number_of_nodes;i++)
		if(visited[i]==false && minimum>distances[i])
		{
			index=i;
			minimum=distances[i];
	
		}

	return index;
}

bool still_has_left(bool *visited,int number_of_nodes)
{
	for(int i=0;i<number_of_nodes;i++)
		if(visited[i]==false)
			return true;
	
	return false;
}

int main()
{
	int number_of_vertices;
	int number_of_arcs;

	FILE *citire=fopen("dijkstra.in","r");
	FILE *scriere=fopen("dijkstra.out","w");
	
	int nothing;

	nothing=fscanf(citire,"%d",&number_of_vertices);
	nothing=fscanf(citire,"%d",&number_of_arcs);

	int **adjacency_matrix;

	adjacency_matrix=(int**)calloc(number_of_vertices,sizeof(int*));

	for(int i=0;i<number_of_vertices;i++)
		adjacency_matrix[i]=(int*)calloc(number_of_vertices,sizeof(int));

	int x,y,cost;

	for(int i=0;i<number_of_arcs;i++)
	{
		nothing=fscanf(citire,"%d%d%d\n",&x,&y,&cost);
		adjacency_matrix[x-1][y-1]=cost;
	}

	bool *visited=calloc(number_of_vertices,sizeof(bool));
	int *distances=calloc(number_of_vertices,sizeof(int));
	int *parent=calloc(number_of_vertices,sizeof(int));
	
	for(int i=0;i<number_of_vertices;i++)
	{
		visited[i]=false;
		distances[i]=10000;
		parent[i]=-1;		
	}

	distances[0]=0;
	

	for(int i=0;i<number_of_vertices;i++)
	{
		int index=get_minimum_unvisited(visited,number_of_vertices,distances,i);

		if(index!=-1)
		{
		visited[index]=true;
		
		for(int j=0;j<number_of_vertices;j++)
			if(adjacency_matrix[index][j]!=0)
				if(distances[j] > distances[index] + adjacency_matrix[index][j])
				{
					distances[j]=distances[index] + adjacency_matrix[index][j];
					parent[j]=index;
				}
		}

		if(still_has_left(visited,number_of_vertices)==false)
			break;
	}



//////////////////////////////////////////////////////////////////////////////////////

	for(int i=1;i<number_of_vertices;i++)
		if(i==number_of_vertices-1)
		{	
			if(distances[i]!=10000)
				fprintf(scriere,"%d\n",distances[i]);
			else
				fprintf(scriere,"0\n");
		}
		else
		{
			if(distances[i]!=10000)
				fprintf(scriere,"%d ",distances[i]);
			else
				fprintf(scriere,"0 ");
		}

	do_nothing(nothing);

	fclose(citire);
	fclose(scriere);

	free(parent);
	free(visited);
	free(distances);
	for(int i=0;i<number_of_vertices;i++)
		free(adjacency_matrix[i]);

	free(adjacency_matrix);


	return 0;
}