///DIJKSTRA
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

typedef pair<int, int> Edge; ///to, cost	

const int INF = numeric_limits<int>::max();

class Comp {public: bool operator () (Edge& a, Edge& b) {return a.second > b.second;}};

void dijkstra(vector<vector<Edge> >& adjList, vector<int>& answ) {
	priority_queue<Edge, vector<Edge>, Comp> pq;

	answ.assign(adjList.size(), INF);
	answ[0] = 0;

	pq.push(Edge(0, answ[0]));

	int cr, crCost;
	vector<Edge>::iterator i;
	while(!pq.empty()) {
		cr = pq.top().first;
		crCost = pq.top().second;
		pq.pop();

		///if(crCost != answ[cr]) continue;

		for(i=adjList[cr].begin(); i!=adjList[cr].end(); ++i) 
			if(answ[cr] + i->second < answ[i->first]) {
				answ[i->first] = answ[cr] + i->second;
				pq.push(Edge(i->first, answ[i->first]));
			}
	}
}

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

	int N, M;
	inStr >> N >> M;

	vector<vector<Edge> > adjList(N);
	
	int fr, to, cst;
	for(int i=0; i<M; ++i) {
		inStr >> fr >> to >> cst;
		adjList[--fr].push_back(Edge(--to, cst));
	}

	vector<int> answ;
	dijkstra(adjList, answ);

	for(int i=1; i<answ.size(); ++i)
		if(answ[i] != INF)
			outStr << answ[i] << ' ';
		else 
			outStr << -1 << ' ';

	outStr << '\n';
	
	return 0;
}