class Pair
{
    int vertex;
    int weight;
    Pair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}
 
class Solution {
    /**
    If you see: "shortest time / delay / distance", weights present, no DAG guarantee
    then Instantly think: Dijkstra
    Idea: give me the node with the smallest distance first using dijkastra algorithm
    */
    public int networkDelayTime(int[][] times, int n, int k) {
 
        // Step-1 Create an adjacency list where each node has {vertex, weight}
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for(int i=0; i<=n; i++)
        {
            adj.add(new ArrayList<Pair>());
        }
 
        for(int[] edge : times)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
 
            adj.get(u).add(new Pair(v,w));
        }
 
        // Step-2 Create a distance array
        int[] distance = new int[n+1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[k] = 0;
 
        // Step-3 Store the nodes into MIN-HEAP accoriding to node's weight to distances
        PriorityQueue<Pair> pq = new PriorityQueue<>(
            (a,b) -> Integer.compare(a.weight, b.weight)
        );
        pq.offer(new Pair(k, 0));
 
        // Step-4 Relax the edges
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int currentNode = pair.vertex;
 
            for(Pair neighbour : adj.get(currentNode))
            {
                int vertex = neighbour.vertex;
                int weight = neighbour.weight;
 
                if(distance[vertex] > distance[currentNode] + weight)
                {
                    distance[vertex] = distance[currentNode] + weight;
                    pq.offer(new Pair(vertex, distance[vertex]));
                }
            }
        }
 
        // Step-5 If any node is unreachable then return -1
        // the distance array contains the shortest path from k to every node.
        int maxDistance = 0;
        for(int i=1; i<=n; i++) 
        {
            if(distance[i] == Integer.MAX_VALUE)
                return -1;
            // maximum of all shortest distances, because that’s when the signal has reached everyone.
            maxDistance = Math.max(maxDistance, distance[i]);
        }
        return maxDistance;
    }
}