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

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

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

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

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

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

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

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

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

    dijkstra(n,graph);

    fclose(input);
    fclose(output);

    return 0;
}

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

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

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

    distance[source] = 0;

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

        used[u] = true;

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

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

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

}

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

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

    return min_index;
}