/*
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) {
        // prepare edges
        List<List<Edge>> edges = new ArrayList<List<Edge>>();

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

        for (int[] time: times) {
            int from = time[0] - 1;
            int to = time[1] - 1;
            int delay = time[2];

            edges.get(from).add(new Edge(to, delay));
        }

        boolean[] processed = new boolean[N];
        boolean[] reached = new boolean[N];
        int[] delays = new int[N];

        // Dijkstra
        int next = K - 1;
        int delay = 0;

        while (next < N) {
            processed[next] = true;
            reached[next] = true;
            delays[next] = delay;

            for (Edge edge: edges.get(next)) {
                if (!reached[edge.node] || (delay + edge.weight < delays[edge.node])) {
                    delays[edge.node] = delay + edge.weight;
                    reached[edge.node] = true;
                }
            }

            next = N;
            delay = Integer.MAX_VALUE;

            for (int i = 0; i < N; i++) {
                if (!processed[i] && reached[i] && delays[i] < delay) {
                    next = i;
                    delay = delays[i];
                }
            }
        }

        // find network delay time
        int max = -1;
        for (int i = 0; i < N; i++) {
            if (!reached[i]) {
                return -1;
            }
            if (delays[i] > max) {
                max = delays[i];
            }
        }

        return max;
    }

    class Edge {
        public int node;
        public int weight;

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