#include <stdio.h>
#include <vector>
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#define NMax 100010

using namespace std;

struct nod
{
	int k;
	int cost;
};

bool operator<(nod a, nod b)
{
	return a.cost > b.cost ;
}

vector<nod> *graf = new vector<nod>[NMax];

int d[NMax];
int p[NMax];
bool selectat[NMax] = {false};

int main()
{
	int a, b, c, n, m, i;
	int sursa, dest;

	ifstream f ("dijkstra.in");
	ofstream g("dijkstra.out");
	f >> n >> m;
	sursa = 1;
	for (i = 0; i < m; i++)
	{
		f >> a >> b >> c;
		nod crt;
		crt.k = b;
		crt.cost = c;
		graf[a].push_back(crt);
	}

	selectat[sursa] = true;
	priority_queue<nod> q;
	nod crt;
	crt.k = sursa;
	crt.cost = 0;

	q.push(crt);

	for (i = 0; i <= n; i++)
		d[i] = INT_MAX / 2;

	for (i = 0; i < graf[sursa].size(); i++)
	{
		d[graf[sursa][i].k] = graf[sursa][i].cost;
		p[graf[sursa][i].k] = sursa;
		q.push(graf[sursa][i]);
	}

	for (i = 1; i <= n; i++)
		selectat[i] = false;

	nod u;

	while (!q.empty())
	{
		u = q.top();
		q.pop();

		if (!selectat[u.k])
		{

			selectat[u.k] = true;

			for (i = 0; i < graf[u.k].size(); i++)
			{
				nod next = graf[u.k][i];
				if ( selectat[next.k] == false &&
				        d[next.k] > d[u.k] + graf[u.k][i].cost)
				{
					d[graf[u.k][i].k] = d[u.k] + graf[u.k][i].cost;
					p[graf[u.k][i].k] = u.k;
					nod nou;
					nou.k = graf[u.k][i].k;
					nou.cost = d[u.k] + graf[u.k][i].cost;
					q.push(nou);
				}
			}
		}
	}

	for (i = 2; i <= n; i++)
		if (d[i] == INT_MAX / 2)
			g << "0 ";
		else
			g << d[i] << " ";







}