#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");

const int INF = 0x3f3f3f3f;
const int SIZE = 50001;

int n, m;

vector <pair <int, int>> V[SIZE];
vector <int> dist(SIZE, INF);
vector <bool> onQueue(SIZE);

struct CompareDistace
{
	bool operator() (int x, int y)
	{
		return dist[x] > dist[y];
	}
};
priority_queue <int, vector <int>, CompareDistace> PQ;

void Read()
{
	f >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, c;
		f >> x >> y >> c;
		V[x].push_back(make_pair(y, c));
	}
}

void Dijkstra(int startNode)
{
	dist[startNode] = 0;
	PQ.push(startNode);
	onQueue[startNode] = true;

	while (PQ.empty() == false)
	{
		int node = PQ.top();
		PQ.pop();
		onQueue[node] = false;

		for (unsigned int i = 0; i < V[node].size(); i++)
		{
			int neighbour = V[node][i].first;
			int cost = V[node][i].second;

			if (dist[neighbour] > dist[node] + cost)
			{
				dist[neighbour] = dist[node] + cost;
				if (onQueue[neighbour] == false)
				{
					PQ.push(neighbour);
					onQueue[neighbour] = true;
				}
			}
		}
	}
}

void Print()
{
	for (int i = 2; i <= n; i++)
	{
		if (dist[i] == INF)
		{
			g << "0 ";
		}
		else
		{
			g << dist[i] << " ";
		}
	}
}

int main()
{
	Read();
	Dijkstra(1);
	Print();
}