#include <stdio.h>
#include <limits.h>
#include <iostream>
#include <fstream>
#include <string>
#include <forward_list>
#include <queue>
using namespace std;

#define MAXNODES 50001

#define IN "dijkstra.in"
#define OUT "dijkstra.out"

struct graph_node
{
	int nodeIndex, edgeValue;
};

struct comparator
{
	bool operator() (int i, int j)
	{
		return i < j;
	}
};

int m, n;
forward_list<graph_node*> adj[MAXNODES];
int dist[MAXNODES];
int min_heap[MAXNODES*3], node_heap_index[MAXNODES], heap_size;

void read_input()
{
	ifstream fin(IN);

	fin >> n;
	fin >> m;
	int from, to, cost;
	for (int i = 0; i < m; ++i)
	{
		fin >> from >> to >> cost;
		graph_node *neigh = new graph_node;
		neigh->nodeIndex = to;
		neigh->edgeValue = cost;
		adj[from].push_front(neigh);
	}
	fin.close();
}

void init_ds()
{
	for (int i = 1; i <= n; ++i)
	{
		dist[i] = INT_MAX;
	}
	dist[1] = 0;
	min_heap[1] = 1;
	heap_size = 1;
	node_heap_index[1] = 1;
}

int get_heap_min_child_index(int heap_index)
{
	if (heap_size == heap_index * 2) // has only left child
		return heap_size;

	if (dist[min_heap[heap_index * 2]] < dist[min_heap[heap_index * 2 + 1]])
		return heap_index * 2;
	else
		return heap_index * 2 + 1;
}

void swap_heap_elems(int i, int j)
{
	int aux = min_heap[i];
	min_heap[i] = min_heap[j];
	min_heap[j] = aux;

	node_heap_index[min_heap[i]] = i;
	node_heap_index[min_heap[j]] = j;
}

void min_heap_bubble_down(int heap_index)
{
	while (heap_size >= heap_index * 2) // has at least one child
	{
		int min_child_heap_index = get_heap_min_child_index(heap_index);
		if (dist[min_heap[heap_index]] > dist[min_heap[min_child_heap_index]])
		{
			swap_heap_elems(heap_index, min_child_heap_index);

			heap_index = min_child_heap_index;
		}
		else
		{
			break;
		}
	}
}

void min_heap_bubble_up(int heap_index)
{
	int heap_parent_index = heap_index / 2;
	while (heap_parent_index > 0)
	{
		if (dist[min_heap[heap_parent_index]] > dist[min_heap[heap_index]])
		{
			swap_heap_elems(heap_parent_index, heap_index);

			heap_index = heap_parent_index;
			heap_parent_index = heap_index / 2;
		}
		else
		{
			break;
		}
	}
}

void push_min_heap(int node_index)
{
	if (node_heap_index[node_index] == 0)
	{
		heap_size++;
		min_heap[heap_size] = node_index;
		node_heap_index[node_index] = heap_size;
	}
	min_heap_bubble_up(node_heap_index[node_index]);
}

int pop_min_heap()
{
	int min_node = min_heap[1];

	swap_heap_elems(1, heap_size);
	heap_size--;

	min_heap_bubble_down(1);

	return min_node;
}

void resolve()
{
	init_ds();

	int nearestNode = 1;
	for (int i = 2; i <= n; ++i)
	{
		if (!adj[nearestNode].empty())
		{
			for (graph_node *x : adj[nearestNode])
			{
				if (dist[x->nodeIndex] > (dist[nearestNode] + x->edgeValue))
				{
					dist[x->nodeIndex] = (dist[nearestNode] + x->edgeValue);
					push_min_heap(x->nodeIndex);
				}
			}
		}
		if (heap_size > 0)
		{
			nearestNode = pop_min_heap();
		}
		else
		{
			break;
		}
	}
}

void print_solution()
{
	ofstream fout(OUT);
	for (int i = 2; i <= n; ++i)
	{
		fout << ((dist[i] == INT_MAX) ? 0 : dist[i]) << ' ';
	}
	fout.close();
}

int main()
{
	read_input();

	resolve();

	print_solution();

	//char x;
	//cin >> x;

	return 0;
}