class Solution {
public int findCheapestPrice(int N, int[][] flights, int src, int dst, int K) {
long[][] dp = new long[N][K + 1];
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], Integer.MAX_VALUE);
}
K = Math.min(K, N - 2);
dp[src][0] = 0;
for (int[] flight : flights) {
int start = flight[0];
int end = flight[1];
int price = flight[2];
if (start == src) {
dp[end][0] = Math.min(dp[end][0], price);
}
}
for (int k = 1; k <= K; k++) {
for (int[] flight : flights) {
int u = flight[0];
int v = flight[1];
int w = flight[2];
dp[v][k] = Math.min(Math.min(dp[v][k - 1], dp[v][k]), dp[u][k - 1] + w);
}
}
return dp[dst][K] == Integer.MAX_VALUE ? -1 : (int)dp[dst][K];
}
}




