#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <time.h>
#include <stdlib.h>
//#include "FibonacciHeap.h"

#define INF (1<<29) - 1

typedef std::pair<int, int> edge;

class comparaPrioritati {
    public:
    bool operator()(edge const &p1, edge const &p2)
    {
        if (p1.second > p2.second)
            return true;
        return false;
    }
};

std::vector<int> shortest_path_Dijkstra(const std::vector<std::vector<edge> >& graph, const int source) {
    std::priority_queue <edge, std::vector<edge>, comparaPrioritati> coadaDePrioritati;
    std::vector<int> dist(graph.size(), INF);
    std::vector<int> viz(graph.size(), 0);
    dist[source] = 0;
    edge act;
    int aux, lungimeNoua, nodDestinatie;
    unsigned int i;
    coadaDePrioritati.push(std::make_pair(source, 0));
    while (!coadaDePrioritati.empty()) {
        act = coadaDePrioritati.top();
        viz[act.first] = 1;
        for (i = 0; i < graph[act.first].size(); ++i) {
            lungimeNoua = graph[act.first][i].second;
            nodDestinatie = graph[act.first][i].first;
            if (lungimeNoua != INF && viz[nodDestinatie] == 0) {
                aux = act.second + lungimeNoua;
                if (aux < dist[nodDestinatie]) {
                    dist[nodDestinatie] = aux;
                    coadaDePrioritati.push(std::make_pair(nodDestinatie, aux));
                }
            }
        }
        coadaDePrioritati.pop();
    }
    return dist;
}

std::vector<int> shortest_path_Dijkstra_FiboHeap(const std::vector<std::vector<edge> >& graph, const int source) {
    FibonacciHeap coadaDePrioritati;
    std::vector<int> dist(graph.size(), INF);
    std::vector<int> viz(graph.size(), 0);
    dist[source] = 0;
    edge act;
    int aux, lungimeNoua, nodDestinatie;
    unsigned int i;
    coadaDePrioritati.insert(std::make_pair(source, 0));
    while (!coadaDePrioritati.isEmpty()) {
        act = coadaDePrioritati.getMinimum();
        viz[act.first] = 1;
        for (i = 0; i < graph[act.first].size(); i++) {
            lungimeNoua = graph[act.first][i].second;
            nodDestinatie = graph[act.first][i].first;
            if (lungimeNoua != INF && viz[nodDestinatie] == 0) {
                aux = act.second + lungimeNoua;
                if (aux < dist[nodDestinatie]) {
                    dist[nodDestinatie] = aux;
                    coadaDePrioritati.insert(std::make_pair(nodDestinatie, aux));
                }
            }
        }
        coadaDePrioritati.removeMinimum();
    }
    return dist;
}

std::vector<int> shortest_path_BellmanFord(const std::vector<std::vector<edge> >& graph, const int source) {
    std::vector<int> dist(graph.size(), INF);
    std::vector<bool> inQueue(graph.size(), false);
    dist[source] = 0;
    std::queue<int> coada;
    coada.push(source);
    int curr, lungimeNoua, nodDestinatie;
    while (!coada.empty()) {
        curr = coada.front();
        inQueue[curr] = false;
        coada.pop();
        for (unsigned int k = 0; k < graph[curr].size(); k++) {
            lungimeNoua = graph[curr][k].second;
            nodDestinatie = graph[curr][k].first;
            if (dist[curr] + lungimeNoua < dist[nodDestinatie]) {
                dist[nodDestinatie] = dist[curr] + lungimeNoua;
                if (!inQueue[nodDestinatie]) {
                    inQueue[nodDestinatie] = true;
                    coada.push(nodDestinatie);
                }
            }
        }
    }

    for (unsigned int j = 0; j < graph.size(); j++) {
        for (unsigned int k = 0; k < graph[j].size(); k++) {
            if (dist[j] + graph[j][k].second < dist[graph[j][k].first]) {
                printf("EROARE graful contine cicluri negative");
                return std::vector<int>();
            }
        }
    }
    return dist;
}

FILE *f = fopen("grader_test999.in", "r");
FILE *g = fopen("dijkstra.out", "w");

int main()
{
    int n, m, start;
    fscanf(f, "%d %d", &n, &m);
    std::vector<std::vector<edge> > graf(n + 1);
    int from, to, cost;
    for (int i = 0; i < m; ++i) {
        fscanf(f, "%d %d %d", &from, &to, &cost);
        graf[from].push_back(std::make_pair(to, cost));
    }
    std::vector<int> dist = shortest_path_Dijkstra(graf, 1);
    for (int i = 1; i < dist.size(); ++i) {
        //if (i != 1)
            fprintf(g, "%d ", dist[i] != INF ? dist[i] : 0);
    }
    /*std::vector<std::vector<edge> > graf2(2000+1);
    int edges = 0;
    srand(time(NULL));
    for(int i = 1; i < 2000; i++) {
        for(int j = 1; j < 2000; j++) {
            if(rand()%100 < 5 && j != i) {
                int cost = rand()%10 + 1;
                graf2[i].push_back(std::make_pair(j, cost));
                //std::cout<<i << " " << j << " " << cost <<"\n";
                edges++;
            }
        }
    }
    std::vector<int> dist2 = shortest_path_Dijkstra(graf2, 1);
    for (int i = 1; i < dist2.size(); ++i) {
        if (i != 1)
            printf("%d ", dist2[i] != INF ? dist2[i] : 0);
    }
    std::cout<<"\n"<<edges<<"\n";*/
    return 0;
}