Dijkstra

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct node
{
    vector <int> polaczenia;
    vector <int> waga;
    int self = 10000000;
};

node graph[1000 * 1000 + 10];

void DajStera(int START = 1)
{
    set < pair <int, int> >  verts;

    graph[START].self = 0;
    verts.insert({0, START});


    int akt,sasiad;
    while(!verts.empty())
    {
        akt = verts.begin()->second;
        verts.erase(verts.begin());

        for(int i = 0; i < graph[akt].waga.size(); i++)
        {
            sasiad = graph[akt].waga[i];

            if(graph[akt].self + graph[akt].waga[i] < graph[sasiad].self)
            {
                if(verts.find({graph[sasiad].self, sasiad}) != verts.end())
                    verts.erase({graph[sasiad].self, sasiad});

                graph[sasiad].self = graph[akt].self + graph[akt].waga[i];

                verts.insert({graph[sasiad].self, sasiad});
            }
        }
    }
}

int main()
{
    int n,m,from, to, cost;
    cin >> n >> m;

    for(int i = 0;i < m; i++)
    {
        cin >> from >> to >> cost;

        graph[from].polaczenia.push_back(to);
        graph[from].waga.push_back(cost);
    }

    DajStera();

    for(int i = 0; i <= n; i++)
        cout << graph[i].self << endl;
}