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

typedef struct priority{

	int vertex1;
	int vertex2;
	int cost;

}Priority;

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

	return false;
}

void do_nothing(int a)
{
}

void remove_the_good_arc(Priority **queue,int* number_of_arcs_in_queue,int good_index)
{

	if((*number_of_arcs_in_queue)==1)
	{
		(*number_of_arcs_in_queue)=0;
			
		free(*queue);
		(*queue)=calloc(1,sizeof(Priority));

	}
	else if(good_index==(*number_of_arcs_in_queue)-1 && (*number_of_arcs_in_queue)>1)
	{
			(*number_of_arcs_in_queue)=(*number_of_arcs_in_queue)-1;
			(*queue)=realloc((*queue),(*number_of_arcs_in_queue)*sizeof(Priority));
	}
	else 
	{
		for(int i=good_index;i<(*number_of_arcs_in_queue)-1;i++)
			(*queue)[i]=(*queue)[i+1];

			
		(*number_of_arcs_in_queue)=(*number_of_arcs_in_queue)-1;

		(*queue)=realloc((*queue),(*number_of_arcs_in_queue)*sizeof(Priority));

	}

}

int compare(const void *a,const void *b)
{
	return  ( (*(Priority*)a).cost - (*(Priority*)b).cost );
}

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",&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));

	Priority *queue=calloc(1,sizeof(Priority));
	int number_of_arcs_in_queue=0;



	for(int i=1;i<number_of_vertices;i++)
	{
		visited[i]=false;

		if(adjacency_matrix[0][i]!=0)
		{
			distances[i]=adjacency_matrix[0][i];
		
			number_of_arcs_in_queue++;

			queue=realloc(queue,(number_of_arcs_in_queue)*sizeof(Priority));

			queue[number_of_arcs_in_queue-1].vertex1=0;
			queue[number_of_arcs_in_queue-1].vertex2=i;
			queue[number_of_arcs_in_queue-1].cost=adjacency_matrix[0][i];

		}
		else
			distances[i]=INT_MAX;

		
	}

	distances[0]=0;
	visited[0]=true;

	int vertex_to_look_through;
	
	
	while(number_of_arcs_in_queue>0)
	{	
		qsort(queue,number_of_arcs_in_queue,sizeof(Priority),compare);
		
		int good_index=0;

		while(1)
		{
			if(visited[queue[good_index].vertex1]==false && visited[queue[good_index].vertex2]==false)
			{
								
				
				printf("da");
			
				break;	
			}
			else if(visited[queue[good_index].vertex1]==false)
			{

				vertex_to_look_through=queue[good_index].vertex1;
				
				break;
			}
			else if(visited[queue[good_index].vertex2]==false)
			{
				vertex_to_look_through=queue[good_index].vertex2;
			
				break;
			}


			good_index++;			

		}

		if(vertex_to_look_through>number_of_vertices)
				break;
		
		remove_the_good_arc(&queue,&number_of_arcs_in_queue,good_index);

		for(int i=1;i<number_of_vertices;i++)
		{
		
			if(adjacency_matrix[vertex_to_look_through][i]!=0)
			{
				if(distances[i] > distances[vertex_to_look_through] + adjacency_matrix[vertex_to_look_through][i])
					distances[i]=distances[vertex_to_look_through] +adjacency_matrix[vertex_to_look_through][i];
		
				number_of_arcs_in_queue++;
	
				queue=realloc(queue,number_of_arcs_in_queue*sizeof(Priority));

				queue[number_of_arcs_in_queue-1].vertex1=vertex_to_look_through;
				queue[number_of_arcs_in_queue-1].vertex2=i;
				queue[number_of_arcs_in_queue-1].cost=adjacency_matrix[vertex_to_look_through][i];


			}
		}

		
		visited[vertex_to_look_through]=true;
		
	}

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

	do_nothing(nothing);

	fclose(citire);
	fclose(scriere);

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

	free(adjacency_matrix);
	free(queue);	

	return 0;
}