#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 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");

	fscanf(citire,"%d",&number_of_vertices);
	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++)
	{
		fscanf(citire,"%d%d%d",&x,&y,&cost);
		adjacency_matrix[x-1][y-1]=cost;
//		adjacency_matrix[y-1][x-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(still_left_to_check(visited,number_of_vertices))
	{	
		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)
			{
								
				while(2)
				printf("da");
				
			}
			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++;			

		}
		
		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)
			fprintf(scriere,"%d\n",distances[i]);
		else
			fprintf(scriere,"%d ",distances[i]);


	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;
}