#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <set>
using namespace std;
#define inf 2e9;

int main() {
	int n,m;
	ifstream fin("catun.in");
	ofstream fout("dijkstra.out");
	fin >> n >> m;
	vector<int> distante;
	vector<int>stramosi;//ca sa tin minte de unde am plecat spre nodul i, nu care e drumul
	vector<list<pair<int, int>>> L; //lista de vecini L[3]={4,7}-> nodul 3 are vecin 4 cu ponderea 7
	set<pair<int, int>> Q; //coada de prioritati


	L.resize(n + 1),distante.resize(n+1),stramosi.resize(n+1);
	for (int i = 1; i <= n; i++)
	{
		stramosi[i] = 0; 
		distante[i] = inf;
	}
	for (int i = 0; i < m; i++)
	{
		int x, y, w;
		fin >> x >> y >> w;
		L[x].push_back({ w,y });
		// L[y].push_back({ w,x }); pt graf neorientat
	}

	int start = 1;
	Q.insert({ 0,start });
	distante[start] = 0;
	stramosi[start] = 0;

	while (!Q.empty()) {
		int nod = Q.begin()->second;
		Q.erase({ distante[nod],nod });
		for (auto p : L[nod])
		{
			int x = p.second;
			int w = p.first;
			if (distante[x] > distante[nod] + w)
			{
				Q.erase({ distante[x], x });
				distante[x] = distante[nod] + w;
				stramosi[x] = nod;
				Q.insert({ distante[x],x });
			}
		}
	}

	for (int i = 2; i <= n; i++)
	{
			cout << distante[i]<<" ";
		
	}
	fin.close();
	return 0;
}