---
# System prepended metadata

title: Untitled

---

    static class Node {
        int index;
        int cost;
        public Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }
    }

    // Complete the shortestReach function below.
    static int[] shortestReach(int n, int[][] edges, int s) {
     // construct returning datasture;
        int[] dist = new int[n];
        for (int i = 0; i<n; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        boolean[] visited = new boolean[n];
        PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                return n1.cost - n2.cost;
            }
        });

        List<List<Node>> adj = new ArrayList<>();
        for (int i = 0; i<n; i++) adj.add(new ArrayList<>());
        for (int i = 0; i<edges.length; i++) {
            int f = edges[i][0]-1;
            int t = edges[i][1]-1;
            int cost = edges[i][2];
            adj.get(f).add(new Node(t, cost));
            adj.get(t).add(new Node(f, cost));
        }

        pq.offer(new Node(s-1, 0));
        int ex = 0;
        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            int curIndex = cur.index;
            if (visited[curIndex]) {
                continue;
            }

            if (cur.cost == 0) ex = cur.index;
            dist[curIndex] = cur.cost;
            visited[curIndex] = true;

            List<Node> neighbors = adj.get(curIndex);
            for (int i = 0; i < neighbors.size(); i++) {
                Node node = neighbors.get(i);
                if (visited[node.index]) continue;

                if (dist[curIndex] + node.cost < dist[node.index]) {
                    dist[node.index] = cur.cost+node.cost;
                    if (!visited[node.index]&&pq.contains(node)) {
                        pq.remove(node);
                        pq.offer(new Node(node.index, dist[node.index]));
                    } else if (!visited[node.index]) {
                        pq.offer(new Node(node.index, dist[node.index]));
                    }
                }
            }
        }

        int[] re = new int[n-1];
        int index = 0;
        for (int i = 0; i < dist.length; i++) {
            if (i == s - 1) continue;
            if (dist[i] == Integer.MAX_VALUE) {
                re[index]  = -1;
            } else {
                re[index] = dist[i];
            }
            index++;
        }

        return re;
    }