OpenJudge

  大年初三的那个晚上，小可可去电影院看了《哈利·波特与魔法石》，回到家坐在椅子上不一会儿就睡着了，并且梦见自己成了哈利·波特驰骋在充满了正义与邪恶的宇宙中执著地为了正义而战。

  那天哈利·波特去拯救Super Samuel星球上的生灵。该星球上有七种不同的地形，依次分别是石子路、森林、草地、山地、雪地、沼泽和沙漠，用数字1～7来表示。任意两个城市之间都存在至少一条通路，而且任意两个能够不经过别的城市而直接通达的城市i和j之间都只存在一种地形t_i,j 。奇怪的是，在Super Samuel星球上哈利·波特穿越地形u所需时间与该地形的区域大小无关，却与地形u的区域中是否有魔法石有关。如果地形u的区域中没有魔法石，哈利·波特要花h_u的时间才能穿越该地区，否则他只要花一半的时间就能穿越了。已知h₁＝2、h₂＝6、h₃＝4、h₄＝8、h₅＝6、h₆＝10、h₇＝14。s_u＝1表示地形u的区域中有魔法石；su＝0表示地形u的区域中没有魔法石。

  例如，如上图所示，有4对可以直接通达的城市（城市1与2、1与3、2与4以及3与4）；s₁＝0、s₂＝1、s₃＝s₄＝s₅＝s₆＝s₇＝0，即只有森林中有魔法石，因此穿越森林所花费的时间是6/2＝3，穿越石子路和草地的时间仍然分别是2和4，如果哈利·波特想从城市1到达城市4，则最快的路线是经过城市2，这条路线需要的时间是2＋3＝5。

  哈利·波特总是忙于铲除邪恶、伸张正义，没有时间去寻找从起点城市i到终点城市j之间的最快路线。现在聘你作为哈利·波特的助手编写程序寻找最快路线为哈利·波特腾出更多的时间来将正义事业进行到底。

0 1 0 0 0 0 0
1 4
4
1 2 1
1 3 1
2 4 2
3 4 3

5