#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 50000;
const int INF = 1 << 30;

struct muchie {
	int nod, cost;

	bool operator>(const muchie& y) const {
		return cost > y.cost;
	}
};

struct {
	vector<muchie> vecini;
	int dist = INF;
} nod[NMAX];

bool cmp(const muchie& x, const muchie& y) {
	return x.cost < y.cost;
}

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);

	int N, M;
	scanf("%d %d\n", &N, &M);

	for (int i = 0; i < N; i++) {
		int v, u, c;
		scanf("%d %d %d\n", &v, &u, &c);
		--v, --u;

		nod[v].vecini.push_back({u, c});
	}

	priority_queue<muchie, vector<muchie>, greater<muchie>> coada;
	coada.push({0, 0});
	nod[0].dist = 0;
	for (; !coada.empty(); coada.pop()) {
		int v = coada.top().nod;
		if (coada.top().cost > nod[v].dist) continue;

		for (auto m: nod[v].vecini) {
			int u = m.nod, c = m.cost;
			if (nod[v].dist + c < nod[u].dist) {
				nod[u].dist = nod[v].dist + c;
				coada.push({u, c});
			}
		}
	}

	for (int v = 1; v < N; v++) {
		int c = nod[v].dist == INF ? 0 : nod[v].dist;
		printf("%d ", c);
	}


	return 0;
}