import Foundation

struct Heap<T: Comparable> {
    var nodes = [T]()
    let sort: (T,T) -> Bool

    init(sort: @escaping (T,T) -> Bool) {
        self.sort = sort
    }

    var isEmpty: Bool {
        nodes.isEmpty
    }

    mutating func append(_ element: T) {
        var index = nodes.count // 마지막 인덱스
        nodes.append(element)

        // shift up
        while index > 0, sort(nodes[index], nodes[(index-1)/2]) {
            nodes.swapAt(index, (index-1)/2)
            index = (index-1)/2
        }
    }

    mutating func pop() -> T? {
        if nodes.isEmpty { return nil }

        // 루트 노드 pop
        let result = nodes.first!
        nodes.swapAt(0, nodes.count - 1)
        nodes.popLast()

        var index = 0

        // shift down
        while index < nodes.count {
            let left = index * 2 + 1
            let right = left + 1

            let children = [left, right]
                .filter { $0 < nodes.count && sort(nodes[$0], nodes[index]) }
                .sorted { sort(nodes[$0], nodes[$1]) }

            if children.isEmpty { break }

            nodes.swapAt(index, children[0])
            index = children[0]
        }

        return result
    }
}

extension Heap {
    init() {
        self.init(sort: <)
    }
}

var heap = Heap<Int>()
heap.append(4)
heap.append(2)
heap.append(3)
heap.append(1)

heap.pop()
heap.pop()
heap.pop()
heap.pop()
heap.pop()

let ve = readLine()!.split(separator: " ").compactMap{Int(String($0))}
let (v,e) = (ve[0], ve[1])    // 정점 개수(V^2 - 400,000,000), 간선 개수(300,000)
let start = Int(readLine()!)! // 시작 정점

let inf = Int.max
var d = [Int](repeating: inf, count: v+1)  // 거리 배열(d, dist, distance)
var adj = Array(repeating: [(Int,Int)](), count: v+1)
var q = Heap<Pair>()

// 방향 그래프 u -> (w) -> v
for _ in 0..<e {
    let uvw = readLine()!.split(separator: " ").compactMap{Int(String($0))}
    let (u,v,w) = (uvw[0], uvw[1], uvw[2])
    adj[u].append((v,w))
}

// 초기 작업
d[start] = 0  // 시작점 초기화
q.push(Pair(d[start], start)) // 시작점 큐에 넣고 시작

// 최단 거리 갱신
while let cur = q.pop() {
  if d[cur.v] != cur.d { continue } // 거리가 가장 작은 원소를 큐에서 선택, 그 값이 테이블에 있는 값과 다르면 skip

  // 현재 정점과 인접해 있는 정점들에 대한 거리 갱신
  for (nxtNode, nxtCost) in adj[cur.v] {
    if d[nxtNode] <= d[cur.v] + nxtCost { continue }

    // 현재 정점을 거쳐가는 것이 더 작다면 갱신
    d[nxtNode] = d[cur.v] + nxtCost   // 테이블 갱신
    q.push(Pair(d[nxtNode], nxtNode)) // 큐에 정점 쌍 추가
  }
}

// 거리 테이블 가지고 출력
for i in stride(from: 1, to: v+1, by: 1) {
  if d[i] == inf { print("INF")}
  else { print(d[i]) }
}

// [유클리드 호제법]
// gcd(a, b) = gcd(b, a % b)
func gcd(_ a: Int, _ b: Int) -> Int {
    if a % b == 0 { return b }
    return gcd(b, a % b)
}

gcd(2, 6)   // 2
gcd(4, 6)   // 2
gcd(12, 8)  // 4
gcd(3, 4)   // 1

func lcm(_ arr: [Int]) -> Int {
    var ret = arr[0]
    for num in arr {
        let gcd = gcd(ret, num)
        ret = gcd * (ret/gcd) * (num/gcd)
    }
    return ret
}

lcm([2, 3])         // 6
lcm([3, 6, 9, 12])  // 36
lcm([3, 4, 7, 13])  // 1092

let N = 1_000_000

// 에라토스테네스의 체 이용
// 일반적인 방법으로 진행하면 시간복잡도가 큼
func countPrimeNumber(_ n:Int) -> Int {
    var prime = Array(repeating: true, count: N+1)
    prime[0...1] = [false, false]

    for i in 2...n {
        if !prime[i] { continue }
        for j in stride(from: i+i, to: n+1, by: i) {
            prime[j] = false
        }
    }

    return prime[0...n].filter { $0 == true }.count
}

countPrimeNumber(13)  // 6(2, 3, 5, 7, 11, 13)

func isPrime(_ n: Int) -> Bool {
    for i in stride(from: 2, to: n, by: 1) {
        if n % i == 0 { return false }
        if i * i > n { break }  // 절반까지만 체크
    }

    return n != 1
}

isPrime(1)
isPrime(2)
isPrime(3)
isPrime(55)
isPrime(13)

func divisor(of num: Int) -> [Int] {
    return (1...num).filter { num % $0 == 0 }
}

divisor(of: 12) // 1, 2, 3, 4, 6, 12
divisor(of: 7)  // 1, 7

func permutation<T: Comparable>(_ target: [T], _ n: Int) -> [[T]] {
  var ret = [[T]]()
  var visited = Array(repeating: false, count: target.count)

  if target.count < n { return ret }

  func recur(_ arr: [T]) {
    if arr.count == n { ret.append(arr); return }
    for i in 0..<target.count {
      if visited[i] { continue }
      visited[i] = true
      recur(arr + [target[i]])
      visited[i] = false
    }
  }

  recur([])
  return ret
}

print(permutation([1, 2, 3], 2))
print(permutation(["a","b","c","d"], 3))

func combination<T: Comparable>(_ target: [T], _ n: Int) -> [[T]] {
  var ret = [[T]]()
  if target.count < n { return ret }

  func recur(_ arr: [T], _ idx: Int) {
    if arr.count == n { ret.append(arr); return }
    for i in idx..<target.count {
      recur(arr + [target[i]], i + 1)
    }
  }

  recur([], 0)
  return ret
}

print(combination([1, 2, 3], 2))
print(combination(["a","b","c","d"], 3))

Int(string_value: radix: n)! // string_value와 n은 같은 진법을 나타내야 함, string 값을 int 타입으로 변환하는 경우 optional로 반환
String(value, radix: n) // 이 때 value는 int 타입(10진수)

2.nonzeroBitCount  // 01
3.nonzeroBitCount  // 11
65.nonzeroBitCount // 1000001
69.nonzeroBitCount // 1000101