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

typedef struct list{

	int number_of_neighbors;
	int *neighbors;
	int *weight;

}AdjacencyList;

void do_nothing(int nothing){}

int get_minimum_unvisited(int *distances,bool *visited,int number_of_vertices)
{
	int index=-1;
	int minimum=INT_MAX;

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

	return index;

}

int main()
{

	FILE *read=fopen("dijkstra.in","r");
	FILE *write=fopen("dijkstra.out","w");

	int number_of_vertices,number_of_arcs;

	fscanf(read,"%d%d",&number_of_vertices,&number_of_arcs);

	AdjacencyList *list=calloc(number_of_vertices+1,sizeof(AdjacencyList));

	int x,y,cost;

	for(int i=0;i<number_of_arcs;i++)
	{
		fscanf(read,"%d%d%d",&x,&y,&cost);
		
		if(list[x].number_of_neighbors==0)
		{
			list[x].number_of_neighbors=1;
			
			list[x].neighbors=calloc(1,sizeof(int));
			list[x].weight=calloc(1,sizeof(int));
			
			list[x].neighbors[0]=y;
			list[x].weight[0]=cost;
	
		}
		else
		{
			list[x].number_of_neighbors++;
				
			list[x].neighbors=realloc(list[x].neighbors,list[x].number_of_neighbors*sizeof(int));
			list[x].weight=realloc(list[x].weight,list[x].number_of_neighbors*sizeof(int));
			
			list[x].neighbors[list[x].number_of_neighbors-1]=y;
			list[x].weight[list[x].number_of_neighbors-1]=cost;

		}
		
	}

	int *distances=calloc((number_of_vertices+1),sizeof(int));
	bool *visited=calloc((number_of_vertices+1),sizeof(bool));

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

	distances[1]=0;

	int index=0;

	while(index!=-1)
	{
		
		index=get_minimum_unvisited(distances,visited,number_of_vertices);


		if(index==-1)
			break;

		visited[index]=true;

		for(int i=0;i<list[index].number_of_neighbors;i++)
		{
			if(distances[list[index].neighbors[i]] > distances[index] + list[index].weight[i])
			{
				distances[list[index].neighbors[i]] = distances[index] + list[index].weight[i];
		
			}

		}

	}



	for(int i=2;i<=number_of_vertices;i++)
	{
		if(i==number_of_vertices)
		{
			if(distances[i]==INT_MAX)
				fprintf(write,"0\n");
			
			else
				fprintf(write,"%d\n",distances[i]);

		}
		else
		{
						
			if(distances[i]==INT_MAX)
				fprintf(write,"0 ");
			
			else
				fprintf(write,"%d ",distances[i]);

		}


	}





//////////////////////////FREE MEMORY/////////////////////////////////////////
		

	free(distances);
	free(visited);
	
	for(int i=1;i<=number_of_vertices;i++)
		if(list[i].number_of_neighbors>0)
		{
			free(list[i].weight);
			free(list[i].neighbors);	
		}

	free(list);	

	fclose(read);
	fclose(write);

	return 0;
}