#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 = a;
		crt.cost = c;
		graf[b].push_back(crt);
		crt.k = b;
		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();
		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++)
		g<<d[i]<<" ";







}