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

#define MAXNODES 50001
#define MAXEDGES 100000

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

struct graph_node
{
	int nodeIndex, edgeValue;
};

int m, n;
forward_list<graph_node> adj[MAXNODES];
int dist[MAXNODES];
bool visited[MAXNODES];

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 initDistance()
{
	for (int i = 2; i <= n; ++i)
	{
		dist[i] = INT_MAX;
	}
}

int getNearestNode()
{
	int minDist = INT_MAX;
	int nearestNode = 0;
	for (int i = 2; i <= n; ++i)
	{
		if (!visited[i] && minDist > dist[i])
		{
			minDist = dist[i];
			nearestNode = i;
		}
	}
	return nearestNode;
}

void resolve()
{
	initDistance();
	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);
				}
			}
		}
		visited[nearestNode] = true;
		nearestNode = getNearestNode();
	}
}

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

int main()
{
	read_input();

	resolve();

	print_solution();

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

	return 0;
}