#include <fstream>
#include <vector>
#include <iostream>
#include <queue>
#include <climits>
using namespace std;
ifstream fileIn("dijkstra.in");
ofstream fileOut("dijkstra.out");


class Graph {
    int N;
    int M;
    vector <vector<pair<int, int>>> list_adj;
    vector<bool> visited;
    vector<int> distance;



    public:
        void read();
        void dijkstra(int start = 1);



};


void Graph:: read() {

    fileIn >> N >> M;
    int a, b, cost;
    list_adj.resize(N+1);
    visited.resize(N+1, false);
    distance.resize(N+1, INT_MAX);
   for ( int i = 0; i < M; i++) {
        fileIn >> a  >> b >> cost;
        list_adj[a].push_back({b, cost});
        cout  << a << " " << b <<" "<<cost <<"\n";
   }

}



void Graph::dijkstra(int start) {
    std::priority_queue<pair<int,int>> pq;
    int curr_node = start;
    distance[curr_node] = 0;
    pq.push({0, curr_node});

    pair<int,int> edge;
    while(!pq.empty()) {
        edge = pq.top();
        pq.pop();
        curr_node = edge.second;
        if (!visited[curr_node]) visited[curr_node] = true;

        for(auto neib: list_adj[curr_node]) {
            int neib_node = neib.first;
            if(!visited[neib_node]) {
                int curr_cost = neib.second + distance[curr_node];
                cout << "curr cost" << curr_cost <<"\n";
                if (curr_cost < distance[neib_node]) {
                    distance[neib_node] = curr_cost;
                    pq.push({-curr_cost, neib_node});
                }
            }
        }

    }


    for(int i = 2; i <= N; i++) {
        if (visited[i]){
                fileOut << distance[i] <<" ";}
        else {
                fileOut << 0 << " ";}
    }

}



int main()  {
    Graph my_graph;
    my_graph.read();
    my_graph.dijkstra(1);


    return 0;



}