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

typedef struct list{

	int number_of_neighbors;
	int *neighbors;
	int *weight;

}AdjacencyList;

typedef struct MinHeap{

	int vertex;
	unsigned int distance;

}Heap;

int max(int a,int b)
{
	if(a<b)
		return b;

	return a;
}

int min(int a,int b)
{
	if(a<b)
		return a;

	return b;
}

void add_to_heap(Heap **minheap,int index)
{
		if(index==1)
			return;

		if((*minheap)[index].distance<(*minheap)[index/2].distance)
		{
			
			int aux=(*minheap)[index].distance;
			(*minheap)[index].distance=(*minheap)[index/2].distance;
			(*minheap)[index/2].distance=aux;						
						
			aux=(*minheap)[index].vertex;
			(*minheap)[index].vertex=(*minheap)[index/2].vertex;
			(*minheap)[index/2].vertex=aux;						
		
			add_to_heap(minheap,index/2);
		}

}

void organize(Heap **minheap,int vertices_in_heap,int index)
{
		if(index*2>vertices_in_heap)
			return;
		else
		{

			int aux;
			if(index*2+1>vertices_in_heap)
			{
				if((*minheap)[index].distance>(*minheap)[index*2].distance)
				{
					aux=(*minheap)[index].distance;
					(*minheap)[index].distance=(*minheap)[2*index].distance;
					(*minheap)[2*index].distance=aux;						
						
					aux=(*minheap)[index].vertex;
					(*minheap)[index].vertex=(*minheap)[2*index].vertex;
					(*minheap)[2*index].vertex=aux;						

					organize(minheap,vertices_in_heap,2*index);
				}	

			}
			else if((*minheap)[2*index].distance == min((*minheap)[2*index].distance,(*minheap)[2*index+1].distance) && (*minheap)[index].distance > (*minheap)[2*index].distance )
			{
				
					aux=(*minheap)[index].distance;
					(*minheap)[index].distance=(*minheap)[2*index].distance;
					(*minheap)[2*index].distance=aux;						
						
					aux=(*minheap)[index].vertex;
					(*minheap)[index].vertex=(*minheap)[2*index].vertex;
					(*minheap)[2*index].vertex=aux;						

					organize(minheap,vertices_in_heap,2*index);
				
			}	
			else if((*minheap)[2*index + 1].distance == min((*minheap)[2*index].distance,(*minheap)[2*index+1].distance) && (*minheap)[index].distance > (*minheap)[2*index+1].distance )
			{
				
					aux=(*minheap)[index].distance;
					(*minheap)[index].distance=(*minheap)[2*index+1].distance;
					(*minheap)[2*index+1].distance=aux;						
						
					aux=(*minheap)[index].vertex;
					(*minheap)[index].vertex=(*minheap)[2*index+1].vertex;
					(*minheap)[2*index+1].vertex=aux;						

					organize(minheap,vertices_in_heap,2*index+1);
				
			}	


		}
		

}

void heapify(Heap **minheap,int index)
{
	if(index==1)
		return;

	if((*minheap)[index].distance<(*minheap)[index/2].distance)
	{
		int aux;

		aux=(*minheap)[index].distance;
		(*minheap)[index].distance=(*minheap)[index/2].distance;
		(*minheap)[index/2].distance=aux;

		aux=(*minheap)[index].vertex;
		(*minheap)[index].vertex=(*minheap)[index/2].vertex;
		(*minheap)[index/2].vertex=aux;


		heapify(minheap,index/2);
	}

}

int main(void)
{

	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;

	int vertices_in_heap=1;

	int real_number_of_vertices=0;

	
	for(int i=0;i<number_of_arcs;i++)
	{
		fscanf(read,"%d%d%d",&x,&y,&cost);
		
		if(max(x,y)>real_number_of_vertices)
		{
			real_number_of_vertices=max(x,y);
			
		}

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

	
	list=realloc(list,(real_number_of_vertices+1)*sizeof(AdjacencyList));
	Heap *minheap=calloc(number_of_vertices+1,sizeof(Heap));
	
	bool *visited=calloc((number_of_vertices+1),sizeof(bool));
	int *distances=calloc((number_of_vertices+1),sizeof(unsigned int));

	for(int i=1;i<=number_of_vertices;i++)
	{
		distances[i]=100000;
		minheap[i].vertex=i;
		minheap[i].distance=100000;
		visited[i]=false;

	}

	minheap[1].vertex=1;
	minheap[1].distance=0;

	distances[1]=0;

	int vertex=0;

	while(vertex!=-1)
	{

		if(vertices_in_heap==0)
			break;

		vertex=minheap[1].vertex;

		if(vertices_in_heap==1)
		{
			vertices_in_heap=0;
			//minheap=realloc(minheap,sizeof(Heap));

		}
		else
		{
			int aux=minheap[vertices_in_heap].vertex;
			minheap[vertices_in_heap].vertex=minheap[1].vertex;
			minheap[1].vertex=aux;

			aux=minheap[vertices_in_heap].distance;
			minheap[vertices_in_heap].distance=minheap[1].distance;
			minheap[1].distance=aux;


			vertices_in_heap--;

			//minheap=realloc(minheap,(vertices_in_heap+1)*sizeof(Heap));
			organize(&minheap,vertices_in_heap,1);
		}
	

	
		if(vertex==-1)
			break;

		visited[vertex]=true;

		
		for(int i=0;i<list[vertex].number_of_neighbors;i++)
		{
			if(visited[list[vertex].neighbors[i]]==false)
			{
				vertices_in_heap++;
			
			//	minheap=realloc(minheap,(vertices_in_heap+1)*sizeof(Heap));
				
				minheap[vertices_in_heap].vertex=list[vertex].neighbors[i];
				minheap[vertices_in_heap].distance= distances[vertex] + list[vertex].weight[i];

				add_to_heap(&minheap,vertices_in_heap);

				if(distances[list[vertex].neighbors[i]] > distances[vertex] + list[vertex].weight[i])
					distances[list[vertex].neighbors[i]] = distances[vertex] + list[vertex].weight[i];

			}

		}

	}








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

		}
		else
		{
						
			if(distances[i]==100000)
				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;
}