题目描述
飞翔很倒霉,在这放假期间也不能休息,被迫找了个兼职帮着发传单⊙﹏⊙汗,然而更倒霉的是,他必须去N个城市去发,而且老板规定不能走最短路线(什么老板啊........),所以他只好找比最短路长但又尽可能短的路了。
给出N个城市,和M条通道,和走这M条通道的长度。并且给出Q,提问Q次,每次提问,给出起始城市的编号和终止城市的编号,输出这两个城市之间的第二短路。
对于20%的数据,有1<=N<=10,1<=Q<=10;
对于50%的数据,有1<=N<=50,1<=Q<=500;
对于100%的数据,有1<=N<=160,1<=Q<=10000,所有道路长度不超过2^10-1。
输入格式
第一行2个数n,m(意义如上所示)
接下来M行,每行3个数,a,b,c,表示a到b有一条长度为c的道路。(2个城市之间最多出现一条道路)。
接下来一行Q
接下来Q行,每行2个数,u,v,即起始和终止城市的编号。
输出格式
对应输出Q行,如果存在第二短路,则输出该长度,否则输出“Fei Xiang can't find the second shortest way!”(不包括双引号)。
样例输入
样例输出