#include <bits/stdc++.h>
using namespace std;

int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
    const int INF = 1e9;
    vector<int> cost(n, INF);
    cost[src] = 0;

    // Relax edges K+1 times (because K stops = K+1 edges)
    for (int i = 0; i <= K; i++) {
        vector<int> temp = cost; // copy previous state
        for (auto& f : flights) {
            int u = f[0], v = f[1], w = f[2];
            if (cost[u] == INF) continue;
            temp[v] = min(temp[v], cost[u] + w);
        }
        cost = temp;
    }

    return cost[dst] == INF ? -1 : cost[dst];
}

int main() {
    int n = 5;
    vector<vector<int>> flights = {
        {0, 1, 100},
        {1, 2, 100},
        {2, 3, 100},
        {3, 4, 100},
        {0, 2, 500}
    };
    int src = 0, dst = 4;

    // Now you can vary K dynamically
    for (int k = 0; k <= 4; k++) {
        cout << "Cheapest with at most " << k << " stops: "
             << findCheapestPrice(n, flights, src, dst, k) << "\n";
    }
    return 0;
}