1import java.util.*;
2
3class Graph {
4    private int n;
5    private List<List<int[]>> adj;
6
7    public Graph(int n, int[][] edges) {
8        this.n = n;
9        this.adj = new ArrayList<>();
10        for (int i = 0; i < n; i++) {
11            adj.add(new ArrayList<>());
12        }
13        for (int[] edge : edges) {
14            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
15        }
16    }
17
18    public void addEdge(int[] edge) {
19        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});
20    }
21
22    public int shortestPath(int node1, int node2) {
23        int[] dist = new int[n];
24        Arrays.fill(dist, Integer.MAX_VALUE);
25        dist[node1] = 0;
26        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
27        pq.offer(new int[]{node1, 0});
28
29        while (!pq.isEmpty()) {
30            int[] current = pq.poll();
31            int u = current[0];
32            int curDist = current[1];
33
34            if (u == node2) return curDist;
35            if (curDist > dist[u]) continue;
36
37            for (int[] neighbor : adj.get(u)) {
38                int v = neighbor[0];
39                int weight = neighbor[1];
40                if (dist[u] + weight < dist[v]) {
41                    dist[v] = dist[u] + weight;
42                    pq.offer(new int[]{v, dist[v]});
43                }
44            }
45        }
46        return -1;
47    }
48
49    public static void main(String[] args) {
50        int[][] edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
51        Graph graph = new Graph(4, edges);
52        System.out.println(graph.shortestPath(3, 2)); // Output: 6
53        System.out.println(graph.shortestPath(0, 3)); // Output: -1
54        graph.addEdge(new int[]{1, 3, 4});
55        System.out.println(graph.shortestPath(0, 3)); // Output: 6
56    }
57}