#include<fstream>
#include<vector>
#include<iterator>
#include<queue>
#define pis pair<int, unsigned short>
#define tempSzomszedok csucs[index].szomszedok
using namespace std;

struct greater {
	bool operator()(pis& bal, pis& jobb) {
		return bal.first > jobb.first;
	}
};
priority_queue < pis, vector <pis>, greater> q;

struct el {
	unsigned short cel, hossz;
};

struct csucsok {
	int tav0 = 2000000000;
	vector<el> szomszedok;
};

void dijkstra(unsigned int index, csucsok *csucs) {
	q.pop();
	vector<el>::iterator it;
	for (it = tempSzomszedok.begin(); it != tempSzomszedok.end(); it++)
		if (csucs[index].tav0 + (*it).hossz < csucs[(*it).cel].tav0) {
			csucs[(*it).cel].tav0 = csucs[index].tav0 + (*it).hossz;
			pis temp; temp.first = csucs[(*it).cel].tav0; temp.second = (*it).cel;
			q.push(temp);
		}
	while (!q.empty() && q.top().first != csucs[q.top().second].tav0)
		q.pop();
	if(!q.empty()) dijkstra(q.top().second, csucs);
}

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

	unsigned short N;
	in >> N;
	csucsok *csucs = new csucsok[N];

	int M;
	for (in >> M;M;--M) {
		unsigned short	A, B, C;
		in >> A >> B >> C;
		el temp;
		temp.cel = B - 1;
		temp.hossz = C;
		csucs[A-1].szomszedok.push_back(temp);
	}
	
	csucs[0].tav0 = 0;
	pis temp;
	temp.first = 0;
	temp.second = 0;
	q.push(temp);
	dijkstra(0,csucs);

	for (int i = 1;i < N;++i)
		out << csucs[i].tav0 << " ";
}