/*
Runtime: 6 ms, faster than 94.73% of Java online submissions for Network Delay Time.
Memory Usage: 49.4 MB, less than 66.67% of Java online submissions for Network Delay Time.
*/
class Solution {
    public int networkDelayTime(int[][] times, int N, int K) {
        List<List<Edge>> graph = new ArrayList<List<Edge>>(N);

        for (int i = 0; i < N; i++) {
            graph.add(new ArrayList<Edge>());
        }

        for (int[] time: times) {
            int from = time[0] - 1;
            int to = time[1] - 1;
            int delay  = time[2];
            graph.get(from).add(new Edge(to, delay));
        }

        int[] delays = new int[N];
        for (int i = 0; i < N; i++) {
            delays[i] = -1;
        }

        calculateDelays(K - 1, graph, delays, 0);

        int maxDelay = -1;

        for (int delay: delays) {
            if (delay == -1) {
                return -1;
            }

            maxDelay = Math.max(maxDelay, delay);
        }

        return maxDelay;
    }

    private void calculateDelays(int from, List<List<Edge>> graph, int[] delays, int delaySoFar) {
        if (delays[from] != -1) {
            if (delays[from] > delaySoFar) {
                delays[from] = delaySoFar;
            }
            return;
        }

        delays[from] = delaySoFar;

        for (Edge edge: graph.get(from)) {
            calculateDelays(edge.node, graph, delays, delaySoFar + edge.delay);
        }
    }

    private class Edge {
        public int node;
        public int delay;

        public Edge(int node, int delay) {
            this.node = node;
            this.delay = delay;
        }
    }
}