Дейкстра O(n^2 + m)

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

using namespace std;

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

int n, m;
int dist[N], used[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;

    while (true) {
        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;

        used[v] = 1;

        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]) {
                dist[u] = dist[v] + len;
            }
        }
    }

    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
***/