#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>
#include <cassert>
#include <iomanip>
#include <climits>


using namespace std;

//```
#define ONLINE_JUDGE

const string file = "dijkstra";
const string inputF = file + ".in";
const string outputF = file + ".out";

const double epsilon = 1e-7;
#define LL long long
#define ULL unsigned long long 
#define MOD1 666013
#define MOD2 666019
#define base 73

typedef vector<int> vi;
typedef vector<long long> vl;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> ii;
typedef pair<long long, long long> ll;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define all(V) V.begin(), V.end()
#define allr(V) V.rbegin(), V.rend()
#define for_c_it(container, it) for (auto it : container)
#define present(container, element) (container.find(element) != container.end()) 
#define sz(a) int((a).size()) 
#define pb push_back 
#define mp make_pair
#define zeroes(x) ((x ^ (x - 1)) & x)


int N, M;
vector<vii> graph;

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#else 
	freopen(inputF.c_str(), "r", stdin);
	freopen(outputF.c_str(), "w", stdout);
#endif

	int i, x, y, c;

	scanf("%d %d", &N, &M);
	//cin >> N >> M;
	graph.resize(N);

	for (i = 0; i < M; ++i) {
		scanf("%d %d %d", &x, &y, &c);
		//cin >> x >> y >> c;
		graph[x - 1].pb(mp(y - 1, c));
	}
	vi dist(N, INT_MAX);
	priority_queue<ii, vii, greater<ii> > heap;
	dist[0] = 0;
	heap.push(mp(0, 0));
	ii node;
	while(!heap.empty()) {
		node = heap.top();
		int from = node.second;
		int d = node.first;
		heap.pop();
		if (dist[from] < d) {
			continue;
		}
		for (auto it: graph[from]) {
			int newD = d + it.second;
			int to = it.first;
			if (dist[to] > newD) {
				dist[to] = newD;
				heap.push(mp(dist[to], to));
			}
		}
	}

	for (i = 1;i < N; ++i) {
		printf("%d ", (dist[i] == INT_MAX ? 0 : dist[i]));
	}
	
	return 0;
}