#include <stdio.h>
#include <stdlib.h>
 
typedef struct list{
 
	int number_of_neighbors;
	int *neighbors;
	int *weight;
 
}AdjacencyList;
 
typedef struct MinHeap{
 
	int vertex;
	unsigned int distance;
 
}Heap;
 
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;
 
	Heap *minheap=calloc(60000,sizeof(Heap));
	int vertices_in_heap=1;
 
	
	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;
		}
		
	}
 
	
	unsigned char *visited=calloc((50002),sizeof(unsigned char));
	int *distances=calloc((50002),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]=0;
	
	} 

	minheap[1].vertex=1;
	minheap[1].distance=0;
 
	distances[1]=0;
 
	int vertex=0;
 
	while(1)
	{
		vertex=minheap[1].vertex;
 
		if(vertices_in_heap==1)
			vertices_in_heap=0;
		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--;
			organize(&minheap,vertices_in_heap,1);
		}
	 
		visited[vertex]=1;
 
		for(int i=0;i<list[vertex].number_of_neighbors;i++)
		{
			if(visited[list[vertex].neighbors[i]]==0)
			{
 
				if(distances[list[vertex].neighbors[i]] > distances[vertex] + list[vertex].weight[i])
				{
					
					vertices_in_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);

					distances[list[vertex].neighbors[i]] = distances[vertex] + list[vertex].weight[i];
 				}
			}
 
		}
		
		if(vertices_in_heap==0)
			break;
 
 
	}
 
  
//////////////////////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]);
 
		}
 
 
	}		
	fclose(read);
	fclose(write);
 
	return 0;
}