Pigeland 的地铁系统非常先进。地铁系统由 座车站构成，编号从 到 ，还有 条有向地铁线，编号从 到 。线路 按顺序经过车站 ，其中 是线路 经过的第 座车站。搭乘线路 从车站 到车站 需要花 单位时间。
当多条线路经过同一车站时，乘客可以在线路之间换乘。若乘客目前位于线路 上的一座车站，而线路 也经过该车站，他/她就能花 单位时间从线路 换乘到线路 ，其中 和 是线路 和 给定的参数。换乘后，乘客位于相同车站的线路 中。
您将从车站 出发。对所有 ，求到达车站 需要的最短时间。更具体地，您可以选择从车站 的任意线路出发，出发时不消耗换乘时间。保证所有车站都能从车站 到达。
