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

using namespace std;

class Graf
{
	int noduri, muchii;

	void Dijkstra(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& q);
public:
	Graf(int n, int m);
	void solve_Dijkstra(ifstream& f, ofstream& o);

};

Graf::Graf(int n, int m)
{
	noduri = n;
	muchii = m;
}

void Graf::Dijkstra(int start, vector<vector<pair<int,int>>>& vecini, vector<int>& d, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& q)
{
	d[start] = 0;

	for (int i = 1; i <= noduri; i++)
		q.push(make_pair(d[i], i));

	while (!q.empty())
	{
		int u = q.top().second; // extragem varful cu eticheta minima din q
		q.pop();
		
		for (auto i = vecini[u].begin(); i != vecini[u].end(); i++) // pentru fiecare muchie uv din E => relaxare
		{
			int v = i->first;
			int lungime = i->second;

			if (d[v] > (d[u] + lungime))
			{
				d[v] = d[u] + lungime; // actualizam lungimea pana la v
				q.push(make_pair(d[v], v));
			}
		}
	}
}

void Graf::solve_Dijkstra(ifstream& f, ofstream& o)
{
	vector<vector<pair<int, int>>>vecini; //liste de adiacenta in care stochez si lungimea

	vecini.resize(noduri + 1);

	for (int i = 0; i < muchii; i++)
	{
		int x, y, cost;

		f >> x >> y >> cost;

		vecini[x].push_back(make_pair(y, cost));
	}

	vector<int>d; // vector in care este stocat costul minim al unui drum de la start la u, descoperit pana la acel moment
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q; // coada de prioritati in care salvez nodurile neselectate inca

	d.resize(noduri + 1, 1000000);

	Dijkstra(1, vecini, d, q);

	for (int i = 2; i <= noduri; i++)
		if (d[i] == 1000000)
			o << 0 << " ";
		else
			o << d[i] << " ";
}

int main()
{
		ifstream f("dijkstra.in");
		ofstream o("dijkstra.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_Dijkstra(f, o);
	
	return 0;
}