#include <stdio.h>
#include <stdlib.h>
#define in "dijkstra.in"
#define out "dijkstra.out"
#define MAX 50001
#define first_node 1
#define infinite 1 << 30

struct edge
{
	long node;
	long value;
	struct edge *next;
};

struct node
{
	int visited;
	struct edge *node;
};

struct node graph[MAX];
long n, dist[MAX], pos[MAX], heap[MAX], heap_length;

//add a new edge to graph
void add_edge(long x, long y, long c)
{	
	//create a new node
	struct edge *new_edge;	
	if ((new_edge = (struct edge *)malloc(sizeof(struct edge))) == NULL)
	{
		printf("Not enoug memory\n");
		exit(-1);
	}	
	new_edge->node = y;
	new_edge->value = c;
	new_edge->next = graph[x].node;
	//add a new tail edge
	graph[x].node = new_edge;
}

void read_file()
{
	FILE *fin;
	long int x, y, m, i, c;
	
	if ((fin = fopen(in, "r")) == NULL)
	{
		printf("Eroare \n");
		exit(-1);
	}
	//read the two nodes
	fscanf(fin, "%ld%ld", &n, &m);
	for (i = 1; i <=n ; i++)
	{
		graph[i].visited = 0;
		graph[i].node = NULL;
	}
	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%ld%ld%ld", &x, &y, &c);		
		//add a new node in graph
		add_edge(x, y, c);
	}
	fclose(fin);
}

void up_heap(long node)
{
	long  father, temp;
	
	while (node > 1)
	{
		father = node / 2;
		if (dist[heap[father]] > dist[heap[node]])
		{
			pos[heap[father]] = node;
			pos[heap[node]] = father;
			
			temp = heap[father];
			heap[father] = heap[node];
			heap[node] = temp;
			
			node = father;			
		}
		else 
		{
			return;
		}
	}
}

void down_heap(long node)
{
	long son, temp;
	
	while (node <= heap_length)
	{
		if (2*node <= heap_length)
		{
			son = 2*node;
			if (son + 1 <= heap_length)
				if (dist[heap[son+1]] < dist[heap[son]])
					son++;
		}
		else
		{
			return;
		}
		if (dist[heap[node]] > dist[heap[son]])
		{
			pos[heap[son]] = node;
			pos[heap[node]] = son;
			
			temp = heap[son];
			heap[son] = heap[node];
			heap[node] = temp;
			
			node = son;		
		}
		else 
		{
			return;
		}
	}
}

void print_heap()
{
	long i;
	for (i = 1; i <= heap_length; i++)
		printf("%ld ", heap[i]);
	printf("\n");
}

void dijkstra()
{
	long i, temp, min_node;
	struct edge *edge;
	for (i = 2; i <= n; i++)
	{
		dist[i] = infinite;
		pos[i] = -1;
	}
	pos[1] = 1;
	dist[1] = 0;
	
	heap[1] = 1;
	heap_length = 1;
	
	while (heap_length != 0)
	{
		min_node = heap[1];

		temp = heap[1];
		heap[1] = heap[heap_length];
		heap[heap_length] = temp;

		heap_length--;		
		down_heap(1);
	
		graph[min_node].visited = 1;
		edge = graph[min_node].node;
		while (edge != NULL)
		{
			if (!graph[edge->node].visited && dist[edge->node] > dist[min_node] + edge->value)
			{
				dist[edge->node] = dist[min_node] + edge->value;
				if (pos[edge->node] == -1)
				{
					heap_length++;
					heap[heap_length] = edge->node;					
					pos[edge->node] = heap_length;
					up_heap(heap_length);
				}
				else
				{
					up_heap(pos[edge->node]);
				}				
			}			
			edge = edge->next;		
		}	
	}	
}

void print_file()
{
	FILE *fout;
	long i;
	fout = fopen(out, "w");
	for (i = 2; i <= n; i++)
		fprintf(fout, "%ld ", dist[i] == infinite ? 0 : dist[i]);
	fclose(fout);
}


int main()
{
	read_file();
	
	dijkstra();
	
	print_file();	

	return 0;
}