题目描述
大家一定记得四强争霸赛中的那个迷宫吧!在今天这个特殊的日子里(哈里波特的生日),三人组一起到哪里开始一场冒险赛。在这个迷宫中,而赫敏则按照最优路径移动,用时t2(聪明,可惜嫁给了个白痴!),哈里由于经验,他会比赫敏晚t2*n时间到达。罗恩因为太傻按照跟着哈里移动。
输入格式
第一行,n(n<=1000),表示迷宫是n个房间的.
以下,表示迷宫的连接情况,和通过所须的时间。
三个人均从(1)开始,(N)结束
除了对角线,其他的0表示两点无边相连!
输出格式
一行,t1,t2分别表示哈里和罗恩,赫敏的到达目标的时间(不能到就输出-1)。
样例输入
样例输出