Форд-Белман

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

using namespace std;

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

int n, m;
int dist[N], a[N], b[N], len[N];

int main(){

    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> len[i];
    }

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

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

    for (int step = 0; step < n; step++) {
        for (int i = 1; i <= m; i++) {
            if (dist[a[i]] + len[i] < dist[b[i]]) {
                dist[b[i]] = dist[a[i]] + len[i];
            }
        }
    }

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