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

int main()
{
	int n,m;
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	vector<int>d, t;
	vector<list<pair<int, int> > > L;// lista de vecini; Ex: L[3]={7,4} -> nodul 3 il are vecin pe 4 prin o muchie de cost 7
	L.resize(n + 1); d.resize(n + 1); t.resize(n + 1);
	for (int i = 1; i <= n; i++)
		t[i] = 0, d[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});


	}

	set<pair<int, int> > Q;

	int start = 1;

	Q.insert({ 0,start });
	d[start] = 0; t[start] = 0;

	while (!Q.empty())
	{
		int nod = Q.begin()->second; 
		Q.erase({ d[nod],nod });//Q.erase(*Q.begin());
		for (auto p : L[nod])
		{
			int x = p.second;
			int w = p.first;
			if (d[x] > d[nod] + w)
			{
				Q.erase({ d[x],x });
				d[x] = d[nod] + w;
				t[x] = nod;
				Q.insert({ d[x],x });
			}
		}
	}
	ofstream fout("dijkstra.out");
	for (int i = 2; i <= n; i++)
		fout << d[i] << " ";



	fin.close();
	return 0;


}