function solution(n, roads, start) {
  const graph = Array.from({ length: n + 1 }, () => []);
  for (const [from, to, cost] of roads) graph[from].push([to, cost]);
  const heap = [];
  const push = (item) => {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[p][0] <= heap[i][0]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const root = heap[0];
    const last = heap.pop();
    if (heap.length === 0) return root;
    heap[0] = last;
    let i = 0;
    while (true) {
      const left = i * 2 + 1;
      const right = left + 1;
      let next = i;
      if (left < heap.length && heap[left][0] < heap[next][0]) next = left;
      if (right < heap.length && heap[right][0] < heap[next][0]) next = right;
      if (next === i) break;
      [heap[i], heap[next]] = [heap[next], heap[i]];
      i = next;
    }
    return root;
  };
  const distance = Array(n + 1).fill(Infinity);
  distance[start] = 0;
  push([0, start]);
  while (heap.length > 0) {
    const [current, node] = pop();
    if (current !== distance[node]) continue;
    for (const [next, cost] of graph[node]) {
      const candidate = current + cost;
      if (candidate >= distance[next]) continue;
      distance[next] = candidate;
      push([candidate, next]);
    }
  }
  return distance.slice(1).map((value) => value === Infinity ? -1 : value);
}