class Solution {

    private static class PQKey {
        double price;
        int stopsFromSource;
        public PQKey(double price, int stopsFromSource) {
            this.price = price;
            this.stopsFromSource = stopsFromSource;
        }
    }

    private static class IndexMinPQ {

        private int maxSize;
        private int[] pq; //holds index at each size of pq;
        private int[] qp; //the inverse of pq, holds the size at each index of the input
        private PQKey[] keys; //these are the values by which we are going to sort PQ
        private int n; //current size of the pq

        public IndexMinPQ(int capacity) {
            this.maxSize = capacity;
            this.keys = new PQKey[maxSize];
            this.pq = new int[maxSize+1]; // +1 because the index is size
            this.qp = new int[maxSize];

            for(int i=0; i < maxSize; i++)
                qp[i] = -1;

        }

        public boolean containsKey(int k) {
            return qp[k] != -1;
        }

        public boolean isEmpty() {
            return n == 0;
        }


        public void insert(int i, PQKey key) {
            n++;
            this.qp[i] = n;
            this.pq[n] = i;
            this.keys[i] = key;
            //System.out.println("i --> " + i + ", n --> " + n + ", i --> " + i);
            swim(n);
        }


        public int[] deleteMin() {
            int[] result = new int[2];

            int min = pq[1];
            result[0] = min;

            exch(1,n--);
            sink(1);
            qp[min] = -1;

            result[1] = keys[min].stopsFromSource;

            keys[min] = null;

            return result;
        }

        public int[] peek() {
             int[] result = new int[2];

              int min = pq[1];
              result[0] = min;
              result[1] = keys[min].stopsFromSource;

              return result;
        }


        public void decreaseKey(int i, PQKey key) {
            this.keys[i] = key;
            swim(qp[i]);
        }

        private void swim(int k) {

            while(k > 1 && greater(k/2,k)) {
                exch(k/2,k);
                k = k/2;
            }

        }


        private void sink(int k) {
            while(2*k <= n) {
                int j = 2*k;
                if(j < n && greater(j,j+1)) j++;
                if(!greater(k,j)) break;
                exch(k,j);
                k = j; //this is very important, it is not k = 2*k;
            }
        }

        private void exch(int i, int j) {

            //i and j are sizes
            //since pq holds holds the size as index
            //exchange pq first

            int swap = pq[i];
            pq[i] = pq[j];
            pq[j] = swap;

            //now exchange corresponding indexes in qp array

            qp[pq[i]] = i; //notice i --> i correspondence, its because pq[i]  has the correct index that needs to change is'v alue
            qp[pq[j]] = j; //notice j --> j correspondence



        }

        private boolean greater(int i, int j) {
            //System.out.println("i --> " + i + ", j --> " + j + ", n --> " + n);

            return keys[pq[i]].price-keys[pq[j]].price > 0 ? true: false;
        }

    }

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {


        int cheapestPrice = Integer.MAX_VALUE;

        //construct digraph

        Map<Integer,List<int[]>> digraph = new HashMap<>();
        int m = flights.length;
        for(int i=0; i < m; i++) {

            int from = flights[i][0];
            if(!digraph.containsKey(from)) {
                digraph.put(from, new ArrayList<>());
            }

            List<int[]> adjList = digraph.get(from);
            adjList.add(flights[i]);
        }


        int[][] edgeTo = new int[n][3];
        double[] distTo = new double[n];

        IndexMinPQ pq = new IndexMinPQ(n);

        for(int i=0; i < n; i++) {
            distTo[i] = Double.POSITIVE_INFINITY;
        }
        distTo[src] = 0;
        pq.insert(src, new PQKey(0,0));

        while(!pq.isEmpty()) {
            int[] minNode = pq.deleteMin();

            int from = minNode[0];
            int stopsFromSource = minNode[1];

            //System.out.println("from --> " + from + ", stopsFromSource --> " + stopsFromSource);

            /*if(stopsFromSource > K){
                continue;
            }*/

            if(from == dst) {
                return (int)distTo[dst];
            }
            if(stopsFromSource <= K) {
                if(digraph.containsKey(from)) {

                    List<int[]> adjList = digraph.get(from);
                    for(int[] edge: adjList) {
                        int v = edge[0];
                        assert v == from;
                        int w = edge[1];
                        System.out.println("v --> " + v + ", w --> " + w);

                         //System.out.println("distTo[w]  --> " + distTo[w]  + ", distTo[v]  --> " + distTo[v] +  ", edge[2]  --> " + edge[2] );


                        if(distTo[w] > distTo[v] + edge[2]) {
                            distTo[w] = distTo[v] + edge[2];
                            edgeTo[w] = edge;

                            System.out.println("distTo[w]  --> " + distTo[w]);

                            if(stopsFromSource < K || (dst == w && stopsFromSource == K)) {


                                 if(pq.containsKey(w)) {
                                    pq.decreaseKey(w, new PQKey(distTo[w],stopsFromSource+1));
                                }
                                else {
                                    pq.insert(w, new PQKey(distTo[w],stopsFromSource+1));
                                }
                            }



                        }

                    }
                }
            }
        }

        return -1;

    }
}