#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, int> IPair;
#define MAX_IPAIR make_pair(INT32_MAX, INT32_MAX)

const int NMAX = 5e4+5;
const int INF = INT32_MAX;

struct Heap {
	vector<IPair> a;
	int size;

	Heap(int maxlen): a(maxlen), size(0) {}

	void down(int r) {
		if(r * 2 > size)
			return;
		if(r * 2 + 1 > size) {
			if(a[r] > a[r * 2])
				swap(a[r], a[r * 2]);
			return;
		}
		int idx = a[r * 2 + 1] < a[r * 2] ? r * 2 + 1 : r * 2;
		if(a[r] > a[idx]) {
			swap(a[r], a[idx]);
			down(idx);
		}
	}

	void up(int x) {
		if (x <= 1)
			return;
		int t = x / 2;
		if (a[x] < a[t]) {
			swap(a[x], a[t]);
			up(t);
		}
	}

	void push(IPair x) {
		a[++size] = x;
		up(size);
	}

	void pop() {
		a[1] = MAX_IPAIR;
		swap(a[1], a[size]);
		down(1);
		size--;
	}

	bool empty() {
		return size == 0;
	}

	IPair top() {
		return a[1];
	}
};

int n, m;
vector<IPair> a[NMAX];
Heap hp(4 * NMAX);
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;
	hp.push({0, 1});

	while (!hp.empty()) {
		int u = hp.top().second;
		hp.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;
				hp.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;
}