dijkstra.cpp

#include <bits/stdc++.h>

using namespace std;

int main(){

    /* freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    */
    int n ,archi;
    cin >> n >> archi ;
    int inizio , fine;
    cin >> inizio >> fine;


    vector<pair<int,int>> v[n];



        int a,b,c;
        for(int i =0;i< archi;i++){
            cin >> a >> b >> c;
            a--;
            b--;
            v[a].push_back({b,c});
            v[b].push_back({a,c});

        }

    ;

    vector<int> dist(n,2e9);


    queue<int> coda;


    coda.push(inizio);
    dist[inizio]=0;

    while(!coda.empty()){

        int ii=coda.front();
        coda.pop();


        for(auto x : v[ii]){

            if(dist[x.first] > dist[ii] + x.second){
                coda.push(x.first);

                dist[x.first] = dist[ii] + x.second;
            }



        }
    }

    cout << dist[fine];

}