#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

#define INF 0x7ffff


std::ifstream fin ("dijkstra.in");
std::ofstream fout ("dijkstra.out");


class Nod {

public:
	int dist;
	std::vector<int> adiacent;
	std::vector<int> cost;
	
};

void solve(int sursa, int N, std::vector<Nod> graf) {		

	for (int i = 1; i <= N; i++) {
		if (i == sursa) graf[i].dist = 0;
		else graf[i].dist = INF;
	}
	
	std::priority_queue<std::pair<int,int> > qu;
	//fist ->index nod;
	//second ->dist sursa - nod
	qu.push(std::make_pair(sursa, 0));	

	
	while (!qu.empty()) {
		std::pair<int,int> n = qu.top();
		graf[n.first].dist = n.second;
		qu.pop();
	
		for (size_t i = 0; i < graf[n.first].adiacent.size(); i++) {
			int lung = graf[n.first].cost[i];
			if (graf[graf[n.first].adiacent[i]].dist > n.second + lung ) {
				qu.push(std::make_pair(graf[n.first].adiacent[i], n.second + lung));
			}
		}
	
	}	

	for (int i = 1; i <= N; i++) {
		if (i != sursa) {
			if (graf[i].dist != INF) fout << graf[i].dist << " ";
			else fout << 0 << " ";
		}
	}

	fout << '\n';
	
}



int main() {


	int N, M;
	fin >> N >> M;

	std::vector<Nod> graf(N+1);
	

	for (int i = 1; i <= M; i++) {
		int x, y, cost;
		
		fin >> x >> y >> cost;
		graf[x].adiacent.push_back(y);
		graf[x].cost.push_back(cost);		
	
	} 
   
	int sursa = 1;
	solve(sursa ,N, graf);

    return 0;
}