Problem1304--盗窃团伙

1304: 盗窃团伙

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 548  Solved: 153
[Submit] [Status] [Web Board] [Creator:]

Description

美丽祥和的CSU校园里有许多门面,每个门面都出租给做生意的商户,商户之间都在做着各自的生意。但是在宁静的校园里也会有邪恶势力存在。CSU存在着一个盗窃团伙麓石开,盗窃团伙为首的是鸡腿xiefang,他们总是想着如何去盗窃所有门面商户的商品,然后疯狂的盗取别人的劳动成果。

现在给定n个门面的路线图,若门面i和门面j有一条直接通路,那么在图里面我们用一条无向边来表示ij可达,边上的权值是门面i和门面j的道路长度。现在鸡腿和xiefang准备在n个门面中选定一个门面租赁,便于偷窃其他所有门面的商品,所以他们对租赁门面的要求是,距离他们租赁门面最远的门面到该门面的路程最短。试问他们应该租赁哪一个门面。


Input

输入第一行包括两个数字n和m , 分别代表CSU的门面数目和门面之间的路径数目( n<=500 m <=10000)。
接下来m行每行输入三个数字 u v w ,代表门面u和门面v之间的距离是w。(1<=u,v <=n , 1<=w <=1000)

Output

输出他们会租赁的门面和与该门面相距最远门面的距离,若有多个合法门面,则输出编号最小的那一个。若他们无法偷窃所有的门面,输出"What a pity!"

Sample Input

3 3
1 2 3
1 3 4
2 3 1

Sample Output

2 3

Source/Category