#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);

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

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;
        graph[y - 1][x - 1] = cost;
    }

    dijkstra(n,graph);

    fclose(input);
    fclose(output);

    return 0;
}

void dijkstra(int n, int **graph) {
    std::vector<std::pair<int,int>> q;
    int source = 0;
    int *distance;

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

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

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

    distance[source] = 0;

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

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

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

    for(int i = 0; i < n; i++) {
        fprintf(output,"%d ", distance[i]);
    }

}