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;
}