#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** initializeMatrix(int n) {

    int** matrix = (int**)malloc(sizeof(int*) * (n + 1));

    for(int i = 0; i <= n; i++) {

        matrix[i] = (int*)malloc(sizeof(int) * (n + 1));
        memset(matrix[i], 0, sizeof(int) * (n + 1));
    }

    return matrix;
}

int* initializeArray(int n, int number) {

    int* array = (int*)malloc(4 * (n + 1));

    for(int i = 0; i <= n; i++)
        array[i] = number;

    return array;
}
void read(FILE* in, int** matrix, int n, int m) {




    int node1, node2, weight;
    for(int i = 0; i < m; i++) {

        fscanf(in, "%d %d %d", &node1, &node2, &weight);
        matrix[node1][node2] = weight;

    }
}

int find(int** matrix, int* visited, int* cost, int n) {

    int node = -1;
    int minCost = 9999999;
    for(int i = 1; i <= n; i++)
        if(visited[i] == 0)
            if(minCost > cost[i]) {

                node = i;
                minCost = cost[i];

            }

    return node;
}

void dijkstra(int** matrix, int n, int* costArray, int* visited, int node) {

    visited[node] = 1;
    for(int i = 1; i <= n; i++) {

        if(visited[i] == 0) {
            if(matrix[node][i] != 0)
                if(costArray[node]  + matrix[node][i] < costArray[i]) {

                    costArray[i] = costArray[node]  + matrix[node][i];
                }
        }
    }

    int nodeNew = find(matrix, visited, costArray, n);

    if(nodeNew != -1)
        dijkstra(matrix, n, costArray, visited, nodeNew);
}

int main() {

    FILE* in = fopen("dijkstra.in", "r");
    FILE* out = fopen("dijkstra.out", "w");
    int n, m;
    fscanf(in, "%d %d", &n, &m);
    int** matrix = initializeMatrix(n);

    read(in, matrix, n, m);

    int* costArray = initializeArray(n, 999999);
    int* visited = initializeArray(n, 0);

    costArray[1] = 0;
    dijkstra(matrix, n, costArray, visited, 1);

    for(int i = 2; i <= n; i++)
        fprintf(out, "%d ", costArray[i]);
    return 0;
}