说明

为了防止牛郎织女相会，王母将二人关在一个岛群中，岛群内有n个小岛，编号从1到n，岛屿之间有鹊桥相连

牛郎在1号岛，织女在n号岛，询问二者能否相遇，如果能相遇最少要用多少时间，在哪里相遇

（PS:牛郎织女整个过程中可以停驻于任意一岛屿内）

输入格式

第一行一个数字t（t<=6），代表测试个数

第二行包括两个数字n，m，(n<=250)分别代表小岛个数和鹊桥个数

接下来m行每行包括3个数字u v w，(w<1500)u v代表相连两岛编号，w代表走过这座桥所需时间

输出格式

若二人无法相遇，输出"kufufufu"

若二者可以相遇，第一行输出相遇所需最短时间，第二行输出相遇时所在小岛

若有多个小岛相遇时间相同，须将所有小岛遍号全部打出

样例

2
5 8
1 2 1
1 3 1
2 3 1
3 4 2
1 5 10
3 4 3
3 5 3
4 5 3
3 1
1 2 1 

3
3 4
kufufufu

提示

桥两个方向都能走