#include <vector>
#include <limits>
#include <cstdio>
#include <cstring>
using namespace std;

struct arc { long int a, b, c; };

int main () {
    long int n, m, i, minim, alt, c;
	const long int infinite = numeric_limits<long int>::max();
	arc d;

	FILE *in = fopen("dijkstra.in", "r");
    fscanf(in, "%ld %ld", &n, &m);

	long int *cost = new long int[n + 1];
    bool *viz = new bool[n + 1];
	arc *arce = new arc[m];

    cost[1] = 0;
    viz[1] = false;
    for (i = 2; i <= n; i++) {
        cost[i] = infinite;
        viz[i] = false;
    }

    for (i = 0; i < m; i++) {
        fscanf(in, "%ld %ld %ld", &arce[i].a, &arce[i].b, &arce[i].c);
        if (arce[i].a == 1) {
            cost[arce[i].b] = arce[i].c;
        }
    }
	fclose(in);

    c = 1;
    while (true) {
        viz[c] = true;
        for (i = 0; i < m; i++) {
            d = arce[i];
            if (d.a == c) {
                alt = cost[c] + d.c;
                if (!viz[d.b] && alt < cost[d.b]) {
                    cost[d.b] = alt;
                }
            }

        }
        minim = infinite;
        for (i = 1; i <= n; i++) {
            if (!viz[i] && cost[i] < minim) {
                minim = cost[i];
                c = i;
            }
        }

        if (minim == infinite) {
            break;
        }
    }

	delete[] viz;
	delete[] arce;

	freopen("dijkstra.out", "w", in);
    for (i = 2; i <= n; i++) {
        fprintf(in, "%ld ", cost[i] == infinite ? 0 : cost[i]);
    }
	fclose(in);

	delete[] cost;

    return 0;
}