#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>

FILE *input = fopen("dijkstra.in","r");
FILE *output = fopen("dijkstra.out","w");

void dijkstra(long long int n, long long int **graph);

long long int getMin(long long int *distances, bool *used, long long int n);

int main() {
    long long int n,m;
    long long int **graph;

    fscanf(input, "%lld %lld", &n, &m);

    graph = (long long int**) malloc(n * sizeof(long long int*));
    for (long long int i = 0; i < n; i++) {
        graph[i] = (long long int*) malloc(n * sizeof(long long int));
    }

    for(long long int i = 0; i < n; i++) {
        for(long long int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }

    for(long long int i = 0; i < m; i++) {
        long long int x, y, cost;
        fscanf(input,"%lld %lld %lld",&x,&y,&cost);
        graph[x - 1][y - 1] = cost;
    }

    dijkstra(n,graph);

    fclose(input);
    fclose(output);

    return 0;
}

void dijkstra(long long int n, long long int **graph) {
    long long int source = 0;
    long long int *distance;
    bool *used;

    distance = (long long int*) malloc(n * sizeof(long long int));
    used = (bool*) malloc(n * sizeof(bool));

    for(long long int i = 0; i < n; i++) {
        distance[i] = INT32_MAX;
        used[i] = false;
    }

    distance[source] = 0;

    for(long long int i = 0; i < n - 1; i++) {
        long long int u = getMin(distance,used,n);

        used[u] = true;

        for(long long int v = 0; v < n; v++) {
            if( !used[v] && (graph[u][v] != 0)  && (distance[u] != INT32_MAX) ) {
                long long int temp = distance[u] + graph[u][v];
                if( temp < distance[v] ) {
                    distance[v] = temp;
                }
            }
        }
    }

    for(long long int i = 1; i < n; i++) {
        if(distance[i] == INT32_MAX) {
            distance[i] = 0;
        }

        fprintf(output,"%lld ", distance[i]);
    }

}

long long int getMin(long long int *distances, bool *used, long long int n) {
    long long int min = INT32_MAX, min_index = 0;

    for (long long int v = 0; v < n; v++)
        if (!used[v] && distances[v] <= min)
            min = distances[v], min_index = v;

    return min_index;
}