import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._
object Main extends App {
  loop
  @tailrec
  def loop: Unit  = {
    val n = readInt
    if (n == 0) return
    val cities = mutable.Map[String, Int]("Tokyo" → 0, "Hakodate" → 1)
    val planes = Array.tabulate(n){_ ⇒
      val Array(start, startTime, arrival, arrivalTime, price) = readLine.trim.split(' ')
      Plane(cities.getOrElseUpdate(start, cities.size), Time.parse(startTime), cities.getOrElseUpdate(arrival, cities.size), Time.parse(arrivalTime), price.toInt)
    }
    val start = Time(8, 0)
    val end = Time(18, 0)
    val planeFrom = Array.tabulate(cities.size){_ ⇒ Nil: List[Plane]}
    val planeTo = Array.tabulate(cities.size){_ ⇒ Nil: List[Plane]}
    planes.filter(p ⇒ p.fromTime >= start && p.toTime <= end).foreach{p ⇒
      planeFrom(p.from) ::= p
      planeTo(p.to) ::= p
    }
    val fromTokyo = calMinCostFrom(0, planeFrom)
    val toTokyo = calMinCostTo(0, planeTo)
    val fromHakodate = calMinCostFrom(1, planeFrom)
    val toHakodate = calMinCostTo(1, planeTo)
    println(
      ( 0 until cities.size).flatMap{c ⇒
        (0 to 570).flatMap(t ⇒ if (List(fromTokyo(c)(t), toTokyo(c)(t + 30), fromHakodate(c)(t), toHakodate(c)(t + 30)).contains(Int.MaxValue)) None else Some(fromTokyo(c)(t) + toTokyo(c)(t + 30) + fromHakodate(c)(t) + toHakodate(c)(t + 30)))
      }.reduceOption(math.min).getOrElse(0)
    )
    loop
  }
  def calMinCostFrom(start: Int, planesFrom: Array[List[Plane]]): Array[Array[Int]] = {
    val memo = Array.tabulate(planesFrom.length){ city ⇒ Array.tabulate(601){ _ ⇒ if (city == start) 0 else Int.MaxValue}}
    val startTime = Time(8, 0)
    val queue = mutable.PriorityQueue()(Ordering.by[(Int, Plane), Int](_._1).reverse)
    for (plane ← planesFrom(start)){
      if (memo(plane.to)(plane.toTime - startTime) > plane.price) {
        memo(plane.to)(plane.toTime - startTime) = plane.price
        queue.enqueue((plane.price, plane))
      }
    }
    while (queue.nonEmpty){
      val (cost, plane) = queue.dequeue()
      if (memo(plane.to)(plane.toTime - startTime) == cost){
        for (p ← planesFrom(plane.to) if p.fromTime >= plane.toTime){
          if (memo(p.to)(p.toTime - startTime) > cost + p.price){
            memo(p.to)(p.toTime - startTime) = cost + p.price
            queue.enqueue((cost + p.price, p))
          }
        }
      }
    }
    for (m ← memo) for (i ← m.indices.tail) m(i) = math.min(m(i), m(i - 1))
    memo
  }
  def calMinCostTo(destination: Int, planesTo: Array[List[Plane]]): Array[Array[Int]] = {
    val memo = Array.tabulate(planesTo.length){ city ⇒ Array.tabulate(601){ _ ⇒ if(city == destination) 0 else Int.MaxValue}}
    val startTime = Time(8, 0)
    val queue = mutable.PriorityQueue()(Ordering.by[(Int, Plane), Int](_._1).reverse)
    for (plane ← planesTo(destination)){
      if (memo(plane.from)(plane.fromTime - startTime) > plane.price) {
        memo(plane.from)(plane.fromTime - startTime) = plane.price
        queue.enqueue((plane.price, plane))
      }
    }
    while(queue.nonEmpty){
      val (cost, plane) = queue.dequeue()
      if (memo(plane.from)(plane.fromTime - startTime) == cost){
        for (p ← planesTo(plane.from) if p.toTime <= plane.fromTime) {
          if (memo(p.from)(p.fromTime - startTime) > cost + p.price){
            memo(p.from)(p.fromTime - startTime) = cost + p.price
            queue.enqueue((cost + p.price, p))
          }
        }
      }
    }
    for (m ← memo) for (i ← m.indices.reverse.tail) m(i) = math.min(m(i), m(i + 1))
    memo
  }
  case class Plane(from: Int, fromTime: Time, to: Int, toTime: Time, price: Int)

  object Time {
    def parse(expression: String): Time = {
      val Array(hour, minute) = expression.split(':').map(_.toInt)
      Time(hour, minute)
    }
  }
  case class Time(hour: Int, minute: Int) extends Ordered[Time]{
    override def compare(that: Time): Int = if (hour == that.hour) minute.compare(that.minute) else hour.compare(that.hour)
    def -(that: Time): Int = hour * 60 + minute - that.hour * 60 - that.minute
  }
}


Measured memory_bytes: 71728