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


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



    public:
        void read();
        void dijkstra(int start = 1);
        void add_edges(int node, std::priority_queue<tuple<int,int, int>> &pq);



};


void Graph:: read() {
    list_adj.resize(N+1);
    visited.resize(N+1, false);
    parent.resize(N+1, 0);
    distance.resize(N+1, 25000);


   fileIn >> N >> M;
   int a, b, cost;

   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::add_edges(int node, std::priority_queue<tuple<int,int,int>> &pq) {
    visited[node] = true;

    for(auto edge: list_adj[node]) {
        if(!visited[edge.first]) {
            pq.push(make_tuple(-edge.second, node ,edge.first));
            cout << "in pq added : " << -edge.second <<  " "<< node<< " "<<edge.first << "\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;
        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;
                    parent[neib_node] = curr_node;
                    pq.push({-curr_cost, neib_node});
                }
            }
        }

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

}



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


    return 0;



}