精灵最近在农场上泛滥，它们经常会阻止牛们从农庄（牛棚 ）走到别的牛棚（牛 的目的地是牛棚 ）。每一个精灵只认识牛 并且知道牛 一般走到牛棚的最短路经。所以它们在牛 到牛棚 之前的最后一条牛路上等牛 。当然，牛不愿意遇到精灵，所以准备找一条稍微不同的路经从牛棚 走到牛棚 。所以，请你为每一头牛i找出避免精灵的最短路经的长度。
和以往一样，农场，上的 条双向牛路编号为 到 并且能让所有牛到达它们的目的地， 个牛棚，牛路 连接牛棚 和 并且需要时间 通过。没有两条牛路连接同样的牛棚，所有牛路满足 。在所有数据中，牛 使用的牛棚 到牛棚 的最短路经是唯一的。
以下是一个牛棚，牛路和时间的例子：
![]()
当精灵进入农场后：
