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

struct greater1{
    bool operator()(const std::pair<int,int>& a,const std::pair<int,int>& b) const{
        return a.second > b.second;
    }
};

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;
    std::vector<std::pair<int,int>> q;
    int *distance = (int*)malloc(n * sizeof(int));

    q.push_back({source,0});
    distance[0] = 0;

    for(int i = 1; i < n; i++) {
        q.push_back({i,INT16_MAX});
        distance[i] = INT16_MAX;
    }

    std::make_heap(q.begin(),q.end(),greater1());

    while(!q.empty()) {
        int u = q.front().first;
        std::pop_heap (q.begin(),q.end()); q.pop_back();

        for(int v = 0; v < n; v++) {
            if( graph[u][v] != 0 ) {
                int temp = distance[u] + graph[u][v];
                if( temp < distance[v] ) {
                    distance[v] = temp;
                    q.push_back({v,distance[v]});
                    std::sort_heap(q.begin(),q.end(),greater1());
                }
            }
        }
    }

    for(int i = 1; i < n; i++) {
        if(distance[i] == INT16_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;
}