import java.util.Scanner
import scala.collection.mutable.{ArrayBuffer, Map}
 
object Main extends App {
  def readALine(c:Int, ac:List[Int]=Nil):List[Int] =
    if (c > 0) readALine(c-1, sc.nextInt::ac) else ac.reverse
  def readLines(r:Int, c:Int, ac:List[List[Int]]):List[List[Int]] =
    if (r > 0) readLines(r-1, c, readALine(c, Nil)::ac) else ac.reverse
  val sc = new Scanner(System.in)
  val numV, numE, start = sc.nextInt
  val lst = readLines(numE, 3, List())

  case class Number(val vid:Int, var cost:Long) extends Ordered[Number] {
    def compare(that:Number) =
      (this.cost, that.cost) match {
        case (a, b) if a > b =>  1
        case (a, b) if a < b => -1
        case _ => 0
      }
  }
   
  class Queue() {
    private val buffer:ArrayBuffer[Number] = ArrayBuffer()
    private def parent(i:Int):Int = (i-1)/2
    private def childL(i:Int):Int = 2*i+1
    private def childR(i:Int):Int = 2*i+2

    private def upHeap(i:Int):Unit = {
      val j = parent(i)
      val p = buffer(j)
      if (i > 0 && p > buffer(i)) {
          buffer(j) = buffer(i)
          buffer(i) = p
          upHeap(j)
      }
    }
    private def downHeap(i:Int):Unit = {
      def inBuffer(x:Int):Boolean = x < buffer.size
      def lessChild(l:Int,r:Int):Int = {
        if (inBuffer(r))
          if (buffer(l) < buffer(r)) l else r
        else l
      }
      val l = childL(i)
      val r = childR(i)
      if (inBuffer(i)) {
        if (inBuffer(l)) {
          val c = lessChild(l, r)
          val p = buffer(i)
          if (p > buffer(c)) {
            buffer(i) = buffer(c)
            buffer(c) = p
            downHeap(c)
          }
        }            
      }
    }
    def enque(x:Number)= {
      buffer+= x
      upHeap(buffer.size-1)
    }
    def deque():Option[Number] = {
      if (buffer.isEmpty) None
      else {
        val r = buffer(0)
        buffer(0) = buffer(buffer.size-1)
        buffer.trimEnd(1)
        downHeap(0)
        Some(r)
      }
    }
    def isEmpty():Boolean = buffer.isEmpty
  }

  class Graph(start:Int, edges:List[List[Int]]) {
    val Infinity:Long = Long.MaxValue >> 2
    val queue = new Queue() // The queue of vertexes
    val varry:Array[Option[Long]] = Array.fill(numV)(None) // The Array of fixed vertexes
    val earry:Array[List[(Int, Int)]] = Array.fill(numV)(List()) // The Map of edges.
    def makeEArray() = for (f::t::w::_ <- edges) earry.update(f, (t, w)::earry(f))
    def nexts(n:Int):List[(Int,Int)] = earry(n)
    def dijkstra():Array[Option[Long]] = {
      def iter():Unit = {
        if (!queue.isEmpty) {
          val number = queue.deque.get
          // println(s"Dequed:$number")
          varry(number.vid) match {
            case Some(x) => if (x > number.cost) varry.update(number.vid, Some(number.cost))
            case None => varry.update(number.vid, Some(number.cost))
          }
          for ((n ,c) <- nexts(number.vid)) {
            val cost = number.cost + c
            varry(n) match {
              case Some(x) if x > cost => queue.enque(Number(n, cost))                   
              case None => queue.enque(Number(n, cost))
              case _ =>
            }
          }
          iter()
        }
      }
      makeEArray()
      queue.enque(Number(start,0))
      iter()
      varry
    }
  }
 
  val graph = new Graph(start, lst)
  for (v <- graph.dijkstra)
     v match {
      case Some(x) => println(x)
      case None => println("INF")
  }

}


Measured memory_bytes: 607556