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

using namespace std;

FILE *input, *output;

#define NMAX 100005
#define INF 1999980005

struct muchie {
	int vf, cost;
};
struct cmp {
	bool operator() (const struct muchie &a, const struct muchie &b) {
		return a.cost > b.cost;
	}
};

priority_queue<struct muchie, vector<struct muchie>, cmp> Q;
vector<struct muchie> C[NMAX];
int d[NMAX];
bool F[NMAX];
int n, m, p;

int main(void) {
	input = fopen("dijkstra.in", "r"), output = fopen("dijkstra.out", "w");
	// input = stdin, output = stdout;

	(void)fscanf(input, "%d %d", &n, &m); p = 1;
	{
		int x, y, cost;
		struct muchie a;

		for (; m > 0; --m) {
			(void)fscanf(input, "%d %d %d", &x, &y, &cost);
			a.cost = cost;
		
			a.vf = y;
			C[x].push_back(a);
			//a.vf = x;
			//C[y].push_back(a);
		}
	}

	{
		int i;
		for (i = 1; i <= n; ++i) d[i] = INF;
	}

	d[p] = 0; F[p] = 1;
	{
		int i;
		for (i = 0; i < C[p].size(); ++i) {
			d[C[p][i].vf] = C[p][i].cost;
			Q.push(C[p][i]);
		}
	}

	{
		int i, j, k;
		while (!Q.empty()) {
			p = Q.top().vf;
			Q.pop();

			if (F[p]) continue;
			F[p] = 1;

			for (i = 0; i < C[p].size(); ++i) {
				j = C[p][i].vf;
				k = C[p][i].cost;
				if (!F[j] && (d[j] > d[p] + k)) {
					d[j] = d[p] + k;
					Q.push(C[p][i]);
				}
			}
		}
	}

	{
		int i;
		for (i = 2; i <= n; ++i) (void)fprintf(output, "%d ", (d[i] < INF) ? d[i] : -1);
		(void)fprintf(output, "\n");
	}

	fclose(output);
	return 0;
}