Дейкстра O(m * log(n))

/***
Графы (Флойд, Дейкстра, Форд Белман)
***/
#include <bits/stdc++.h>

using namespace std;

const int N = 5005;
const int inf = 2e9;

int n, m;
int dist[N];
vector < pair <int, int> > g[N];

int main(){

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int u, v, len;
        cin >> u >> v >> len;
        g[u].push_back(make_pair(v, len));
        g[v].push_back(make_pair(u, len));
    }

    for (int i = 0; i < N; i++) {
        dist[i] = inf;
    }

    int start;
    cin >> start;
    dist[start] = 0;

    set < pair <int, int> > st;
    st.insert(make_pair(dist[start], start));

    while (!st.empty()) {
//        int v = -1;
//        for (int i = 1; i <= n; i++) {
//            if (used[i] == 0 && (v == -1 || dist[v] > dist[i])) {
//                v = i;
//            }
//        }
//        if (v == -1) break;
        int v = st.begin()->second;
        st.erase(st.begin());

        for (int i = 0; i < g[v].size(); i++) {
            int u = g[v][i].first, len = g[v][i].second;
            if (dist[v] + len < dist[u]) {
                st.erase(make_pair(dist[u], u));
                dist[u] = dist[v] + len;
                st.insert(make_pair(dist[u], u));
            }
        }
    }

    int finish;
    cin >> finish;

    if (dist[finish] == inf) {
        cout << "No path\n";
    } else {
        cout << dist[finish] << endl;
    }
}
/**
6 8
1 2 2
1 3 3
3 5 1
2 5 2
2 4 4
5 4 1
5 6 5
4 6 2
1 6
***/