class Pair {
    int stop, node, cost;
    public Pair(int stop, int node, int cost)
    {
        this.stop = stop;
        this.node = node;
        this.cost = cost;
    }
}
 
class iPair{
    int first, second;
    public iPair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // creating adjancency list
        ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
        for(int i=0;i<n;i++)
            adj.add(new ArrayList<iPair>());
 
        for(int[] edge : flights)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
 
            adj.get(u).add(new iPair(v, w));
        }
 
        // Distance array to store the updated distances from the source. 
        int[] distance = new int[n];
        Arrays.fill(distance, (int)1e9);
        distance[src] = 0;  
 
        // Queue <stop, node, cost>
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(0,src,0));
 
        while(!q.isEmpty())
        {
            Pair pair = q.poll();
            int stop = pair.stop;
            int node = pair.node;
            int cost = pair.cost;
 
            // We stop the process as soon as the limit for the stops reaches.
            if(stop>k)
                continue;
 
            for(iPair neighbour : adj.get(node))
            {
                int adjNode = neighbour.first;
                int adjWeight = neighbour.second;
 
                // We only update the queue if the new calculated distance
                // less than the prev and the stops are also within limits.
                if(distance[adjNode] > (cost + adjWeight) && stop <= k)
                {
                    distance[adjNode] = cost + adjWeight;
                    q.add(new Pair(stop+1, adjNode, distance[adjNode]));
                }
            }
        }
        // If the destination node is unreachable return ‘-1’
        // else return the calculated dist from src to dst.
        if(distance[dst] == Integer.MAX_VALUE)
            return -1;
        return distance[dst];
    }
}