ダイクストラ法 (Dijkstra's Algorithm)

let input = require("fs").readFileSync("/dev/stdin", "utf8");
const lines = input.trim().split("\n");

let v, e, r, path = []

for (let i = 0; i < lines.length; i++) {
  if (i === 0) {
    [v, e, r] = lines[i].split(" ").map((v) => parseInt(v));
    path = [...Array(v)].map(() => new Set());
    continue;
  }
  const [s, t, d] = lines[i].split(" ").map((v) => parseInt(v));
  path[s].add([t, d])
}

const parent = (i) => Math.floor((i - 1) / 2)
const leftChild = (i) => 2 * i + 1
const rightChild = (i) => 2 * i + 2

const MinHeap = function (n) {
  this.a = [...Array(n).keys()].map(v => [v, Number.MAX_SAFE_INTEGER]) // [vertex, weight]
  this.pos = [...Array(n).keys()].map(v => v)
  this.size = n
}

MinHeap.prototype.extractMin = function () {
  const [v, w] = this.a[0]
  this.swap(0, this.size - 1)
  this.size--
  this.popDown(0)
  return [v, w]
}

MinHeap.prototype.swap = function (i, j) {
  const vi = this.a[i][0], vj = this.a[j][0];
  [this.a[i], this.a[j]] = [this.a[j], this.a[i]];
  [this.pos[vi], this.pos[vj]] = [this.pos[vj], this.pos[vi]]
}

MinHeap.prototype.decreaseKey = function (v, val) {
  const i = this.pos[v]
  this.a[i][1] = val
  this.popUp(i)
}

// vertexが含まれているか
MinHeap.prototype.contains = function (v) {
  return this.pos[v] < this.size
}

// 適切な位置まで上げる
MinHeap.prototype.popUp = function (i) {
  let pi = parent(i)
  while (i > 0 && this.a[i][1] < this.a[pi][1]) { // 親が子より大きかったら交換
    this.swap(i, pi)
    i = pi
    pi = parent(i)
  }
}

// 値を取得
MinHeap.prototype.val = function (v) {
  return this.a[this.pos[v]][1]
}

// 適切な位置まで下げる
MinHeap.prototype.popDown = function (i) {
  const val = this.a[i][1]
  let candidate = null // 子供のほうが小さかったら交換
  const ri = rightChild(i)
  const li = leftChild(i)
  if (ri < this.size) { // right child exist
    if (this.a[ri][1] < val) {
      candidate = ri
    }
  }
  if (li < this.size) {
    if (candidate == null) {
      if (this.a[li][1] < val) {
        candidate = li
      }
    } else {
      if (this.a[li][1] < this.a[ri][1]) {
        candidate = li
      }
    }
  }
  if (candidate != null) {
    this.swap(i, candidate)
    this.popDown(candidate)
  }
}


function dijkstra(n, r, path) {
  const minHeap = new MinHeap(n)
  const dist = Array(n).fill(null)
  const parent = Array(n).fill(null)

  // initialization
  minHeap.decreaseKey(r, 0)
  dist[r] = 0

  while (minHeap.size > 0) {
    const [u, d] = minHeap.extractMin()
    for (const [v, w] of path[u]) {
      if (!minHeap.contains(v)) {
        continue
      }
      if (d + w < minHeap.val(v)) {
        parent[v] = u
        dist[v] = d + w
        minHeap.decreaseKey(v, d + w)
      }
    }
  }

  for (const d of dist) {
    if (d == null) {
      console.log('INF')
    } else {
      console.log(d)
    }
  }
}


// console.log(v, e, r)
// console.log(path)
dijkstra(v, r, path)