// dijkstra.cpp : This file contains the 'main' function. Program execution begins and ends there.
//
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

const int nMax = 50001;
const int INF = (1 << 30);
int n, m;
vector <pair <int, int>> L[nMax]; // L.first = nodul destinatie, L.second = costul de a ajunge
priority_queue <pair <int, int>> q; // pentru a tine valorile in ordine crescatoare vom pusha valori negative pt distante
                                    // q.first = distanta de a ajunge in nod, q.second = nodul sursa
                                    // priority queue sorteaza automat in functie de first
bool viz[nMax];
int dist[nMax]; // d[i] = distanta de la nodul 1 la nodul i

void Read() {
    ifstream fin("dijkstra.in");
    fin >> n >> m;
    int x, y, d;
    for (int i = 0; i < m; i++) {
        fin >> x >> y >> d;
        L[x].push_back({y, d});
    }
    fin.close();
}

void Dijkstra(int nod) { // nod este nodul de start 
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
    }
    dist[nod] = 0;
    q.push({ 0, nod });
    while (!q.empty()) {
        int nod = q.top().second; // nodul in care sunt
        int cost = -q.top().first; // costul cu care am ajuns in nod
        q.pop();
        if (!viz[nod]) { // daca nu am mai trecut prin acest nod
            viz[nod] = 1; // il marchez ca vizitat
            for (auto it : L[nod]) { // parcurg vecinii nodului 1
                int newNod = it.first; // nodul in care vreau sa ma duc
                int newCost = it.second; // costul pentru a ajunge din nod in newNod
                if (dist[newNod] > dist[nod] + newCost) { // actualizez distantele daca este cazul
                    dist[newNod] = dist[nod] + newCost;
                    q.push({ -dist[newNod], newNod });
                }
            }
        }
    }

    // afisarea distantelor
    ofstream fout("dijkstra.out");
    for (int i = 2; i <= n; i++) {
        if (dist[i] == INF) fout << "0 ";
        else fout << dist[i] << " ";
    }
    fout << "\n";
}

int main()
{
    Read();
    Dijkstra(1);
    return 0;
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file