/**
 * Created by m00nlight on 7/27/15.
 */


import scala.collection.mutable
import scala.math.Ordering.Implicits._
import scala.collection.mutable.HashMap

class Graph[N : Ordering, E : Numeric] {

  def dijkstra(graph : Map[N, List[Tuple2[N, E]]], source : N): HashMap[N, E] = {
    val pq = new mutable.PriorityQueue[Tuple2[E, N]]()
    val ret = new HashMap[N, E]()
    ret += Tuple2(source, 0.asInstanceOf[E])
    pq.enqueue((0.asInstanceOf[E], source))

    while (! (pq isEmpty)) {
      val (dis, node) = pq.dequeue()
      val updated = graph.get(node) match {
        case None => List()
        case Some(xs) => xs.filter {
          case (n, e) => {
            ret.get(n) == None || (dis < implicitly[Numeric[E]].plus(ret.get(n).get, e))
          }
        }
      }

      val tmp = updated.map {x => (x._1, implicitly[Numeric[E]].plus(dis, x._2))}
      ret ++= tmp
      for (x <- tmp) pq.enqueue((x._2, x._1))
    }
    ret
  }

  def buildGraph(edges : List[Tuple3[N, N, E]]) : Map[N, List[Tuple2[N, E]]]  = {
    edges.groupBy(_._1).map {
      case (k, v) => (k, v.map {x => (x._2, x._3)})
    }
  }
}


object Main {
  def main(args: Array[String]) {
    val in = io.Source.fromFile("src/test.in")
    //val in = io.Source.createBufferedSource(System.in)
    val xs = in.getLines().toList.map{ x => x.split("\\s+").map(_.toInt)}.map {x => (x.head, x.tail.head, x.last)}
    val graph = new Graph[Int, Int]()
    val res = graph.dijkstra(graph.buildGraph(xs.tail), xs.head._3)
    for (x <- Range(0, xs.head._1)) {
      res.get(x) match {
        case None => println("INF")
        case Some(x) => println(x)
      }
    }
  }
}