fun jackGoesToRapture(N: Int, edges: Array<Array<Int>>): Int? {
    val nodeList = (1..N).map { Node(it) }
    for (edge in edges) {
        val a = edge[0]
        val b = edge[1]
        val cost = edge[2]
        nodeList[a-1].connections[nodeList[b-1]] = cost
        nodeList[b-1].connections[nodeList[a-1]] = cost
    }
    val queue = PriorityQueue<NodeAndCost>(compareBy { it.cost })
    val distances = mutableMapOf<Node, Int>()
    queue.add(NodeAndCost(nodeList[0], 0))
    distances[nodeList[0]] = 0
    
    while (!queue.isEmpty()) {
        val n0 = queue.remove().node
        val roads = n0.connections
        for (n in roads.keys) {
            val cost = kotlin.math.max(roads[n]!!, distances[n0]!!)
            if (cost < distances[n] ?: Int.MAX_VALUE) {
                distances[n] = cost
                queue.add(NodeAndCost(n, cost))
            }
        }
    }
    return distances[nodeList[nodeList.size - 1]]
}

data class Node(val name: Int) {
    val connections: MutableMap<Node, Int> = mutableMapOf()
}

data class NodeAndCost(val node: Node, var cost: Int)

class Edge {
        int to, weight;

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

     class Node implements Comparable<Node> {
        int id;
        long cost;

        public Node(int id, long cost) {
            this.id = id;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node other) {
            return Long.compare(this.cost, other.cost);
        }
    }

     class Result {
        public static void getCost(int gNodes, List<Integer> gFrom, List<Integer> gTo, List<Integer> gWeight) {
            List<List<Edge>> graph = new ArrayList<>(gNodes + 1);
            for (int i = 0; i <= gNodes; i++) {
                graph.add(new ArrayList<>());
            }

            for (int i = 0; i < gFrom.size(); i++) {
                int from = gFrom.get(i);
                int to = gTo.get(i);
                int weight = gWeight.get(i);
                graph.get(from).add(new Edge(to, weight));
                graph.get(to).add(new Edge(from, weight));
            }

            long[] dist = new long[gNodes + 1];
            Arrays.fill(dist, Long.MAX_VALUE);
            dist[1] = 0;

            PriorityQueue<Node> pq = new PriorityQueue<>();
            pq.add(new Node(1, 0));

            while (!pq.isEmpty()) {
                Node current = pq.poll();
                int u = current.id;
                long currentCost = current.cost;

                if (currentCost > dist[u]) continue;

                for (Edge edge : graph.get(u)) {
                    int v = edge.to;
                    long newCost = edge.weight;

                    if (currentCost < newCost) {
                        newCost -= currentCost;
                    } else {
                        newCost = 0;
                    }

                    if (dist[u] + newCost < dist[v]) {
                        dist[v] = dist[u] + newCost;
                        pq.add(new Node(v, dist[v]));
                    }
                }
            }

            long result = dist[gNodes];
            if (result == Long.MAX_VALUE) {
                System.out.println("NO PATH EXISTS");
            } else {
                System.out.println(result);
            }
        }
    }

def getCost(g_nodes, g_from, g_to, g_weight):
    # Uses Prim's algorithm to find minimal spanning tree starting from node 1, stop as soon as goal is is put in the tree. At each step record the weight of the longest edge. This weight is necessarily in the path from 1 to goal in the MSP, and will be the answer. If when the tree is done and goal is still not reached, it means no path exists.
    from heapq import heappush, heappop
    # adjacency matrix
    adj = [[] for _ in range(g_nodes + 1)]
    for i in range(len(g_weight)):
        adj[g_from[i]].append((g_weight[i], g_to[i]))
        adj[g_to[i]].append((g_weight[i], g_from[i]))
    # record which node is visited
    visited = [False, True] + [False]*(g_nodes-1)
    # adjacent edges to the tree so far. Use heap to find the one with lowest weight.
    adj_edge = []
    for edge in adj[1]:
        heappush(adj_edge, edge)
    maximum = float('-inf')

    while True:
        # pop the adjacent edge with lowest weight
        new_weight, new_node = heappop(adj_edge)
        while visited[new_node]:
            if len(adj_edge) == 0:
                print('NO PATH EXISTS')
                return
            new_weight, new_node = heappop(adj_edge)
        visited[new_node] = True
        maximum = max(maximum, new_weight)
        # if the new node just added is the goal, then we're done
        if new_node == g_nodes:
            print(maximum)
            return
        #update adjacent edges
        for edge in adj[new_node]:
            heappush(adj_edge, edge)
        
#use adjacency matrix and heap