#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

#ifdef LOCAL
ifstream fin("input.txt");
#define fout cout
#else
class InParser {
private:
	FILE *fin;
	char *buff;
	int sp;

	char read_ch() {
		++sp;
		if (sp == 4096) {
			sp = 0;
			fread(buff, 1, 4096, fin);
		}
		return buff[sp];
	}

public:
	InParser(const char* nume) {
		fin = fopen(nume, "r");
		buff = new char[4096]();
		sp = 4095;
	}
	
	InParser& operator >> (int &n) {
		char c;
		while (!isdigit(c = read_ch()) && c != '-');
		int sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
	
	InParser& operator >> (long long &n) {
		char c;
		n = 0;
		while (!isdigit(c = read_ch()) && c != '-');
		long long sgn = 1;
		if (c == '-') {
			n = 0;
			sgn = -1;
		} else {
			n = c - '0';
		}
		while (isdigit(c = read_ch())) {
			n = 10 * n + c - '0';
		}
		n *= sgn;
		return *this;
	}
} fin("dijkstra.in");
ofstream fout("dijkstra.out");
#endif

typedef pair<int, uint16_t> IPair;

const int NMAX = 5e4+5;
const int INF = 2e9;

int n, m;
vector<IPair> a[NMAX];
priority_queue<IPair, vector<IPair>, greater<IPair>> pq;
int dist[NMAX];

void read() {
	fin >> n >> m;
	int x, y, d;
	while (m--) {
		fin >> x >> y >> d;
		a[x].push_back({y, d});
	}
}

void solve() {
	for (int i = 2; i <= n; i++)
		dist[i] = INF;
	pq.push({0, 1});

	while (!pq.empty()) {
		int u = pq.top().second;
		pq.pop();
		for (auto &it : a[u]) {
			int v = it.first;
			int d = it.second;
			if (dist[v] > dist[u] + d) {
				dist[v] = dist[u] + d;
				pq.push({dist[v], v});
			}
		}
	}

	for (int i = 2; i <= n; i++)
		fout << (dist[i] != INF ? dist[i] : 0) << ' ';
}

int32_t main() {
	read();
	solve();
	return 0;
}