#include <bits/stdc++.h>
#define pii pair<int,int>
#pragma GCC optimize("O3")

using namespace std;

class InParser {
private:
	FILE * fin;
	char * buff;
	int sp;

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

public:
	InParser(const char * nume) {
		fin = fopen(nume, "r");
		buff = new char[16384]();
		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;
	}
};
InParser fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int nmax = 5e4, inf = 2e9;

vector<pair<int, int>> edge[nmax + 1];
vector<int> minn(nmax + 1, inf);

int n, m, x, y, c;

void djikstra() {
	priority_queue<pii, vector<pii>, greater<pii>> pq;
	pq.push({0, 1});
	minn[1] = 0;
	while(pq.empty() == 0) {
		int cc = pq.top().first, cn = pq.top().second;
		pq.pop();
		if(minn[cn] < cc)
			continue;
		for(auto nxt : edge[cn]) {
			int nc = cc + nxt.second, nn = nxt.first;
			if(minn[nn] > nc) {
				minn[nn] = nc;
				pq.push({nc, nn});
			}
		}
	}
}

int main() {
	fin >> n >> m;
	for(int i = 1; i <= m; i++) {
		fin >> x >> y >> c;
		edge[x].push_back({y, c});
	}
	djikstra();
	for(int i = 2; i <= n; i++)
		fout << ((minn[i] == inf) ? 0 : minn[i]) << " ";
	return 0;
}