#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <utility>
#include <string>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <limits>
#include <sstream>
#include <deque>
#include <bitset>
#include <complex>
#include <functional>
#include <memory>
#include <numeric>

using namespace std;

#define x first
#define y second

struct lessp {
	bool operator()(pair<int, int> const &l, pair<int, int> const &r) {
		return l.x < r.x;
	}
};

int main () {
	vector<pair<int, int>> G[50002];
	vector<int> C(50002, 1<<30);
	vector<int> gotC(50002, 0);
	
	int n, m;
	FILE *in, *out;
	in = fopen("dijkstra.in", "rt");
	out = fopen("dijkstra.out", "wt");


	fscanf(in, "%d %d", &n, &m);

	for(int i = 0; i < m; i++) {
		int s, e, c;
		fscanf(in, "%d %d %d", &s, &e, &c);
		G[s].push_back({e, c});
	}


	priority_queue<pair<int, int>, vector<pair<int, int>>, lessp> q;
	q.push({0, 1});
	C[1] = 0;

	while(!q.empty()) {
		auto c = q.top();
		q.pop();

		//if(gotC[c.y]) continue;
		for(int i = 0; i < G[c.y].size(); i++){
			if(C[G[c.y][i].x] > C[c.y] + G[c.y][i].y) {
				C[G[c.y][i].x] = C[c.y] + G[c.y][i].y;
				q.push({C[G[c.y][i].x], G[c.y][i].x});				
			}
		}
		gotC[c.y] = 1;		
	}
	
	for(int i = 2; i <= n; i++) {
		fprintf(out, "%d ", (C[i] == 1<<30 ? 0 : C[i]));
	}
	fprintf(out, "\n");

	return 0;
}