BELLMAN FORD

class Solution:
    def findCheapestPrice(self, n: int, f: List[List[int]], src: int, dst: int, K: int) -> int:
        dist = [float("inf") for i in range(n)]
        dist[src] = 0
        for _ in range(K+1):
            backup = dist[:]
            for i in range(len(f)):
                a, b, w = f[i][0], f[i][1], f[i][2]
                dist[b] = min(dist[b], backup[a] + w)
        return dist[dst] if dist[dst] != float("inf") else -1