Acesrc and his girlfriend are famous sweet lovers at Nanjing University second to none. They often wander along the streets near Xinjiekou, and taste takoyaki.
Xinjiekou is the central business district of Nanjing, consisting of nn crossroads and mm streets connecting some pairs of these crossroads. By every street there is a takoyaki bar, and Acesrc has a preference value for each of these bars. The streets are bidirectional.
Acesrc and his girlfriend choose a pair of crossroads as the starting point and the ending point; moreover, they choose a route between these two crossroads, and they walk along the streets in the route. Every crossroad appears in the route at most once. Once they encounter a takoyaki bar they will buy a serve of takoyaki from this bar. However, they can keep at most two serves of takoyaki. If, after buying a serve of takoyaki they have more than two serves, they will discard one serve with minimum preference value.
After reaching the ending point they begin to enjoy the takoyaki. Acesrc always eats the serve with lower preference value; however, if they only bought one serve, poor Acesrc will have nothing to eat. The clever Acesrc wants to know the minimum possible preference value of the serve he eats, given the starting point and the ending point of their route. Can you tell him the value?
Input
The first line of input consists of a single integer TT(1≤T≤100)(1≤T≤100), the number of test cases.
For each test case, the first line consists of three integers n,m,qn,m,q(1≤n,q≤105,1≤m≤2×105)(1≤n,q≤105,1≤m≤2×105), denoting the number of crossroads, streets in Xinjiekou, and the number of queries, respectively. Each of the next mm lines contains three integers x,y,wx,y,w(1≤x,y≤n,x≠y,1≤w≤109)(1≤x,y≤n,x≠y,1≤w≤109), denoting a street connecting the xxth and the yyth crossroads, with a takoyaki bar of preference value wwnear the street. It is possible that multiple streets connect the same pair of crossroads. Each of the last qq lines are two integers u,vu,v(1≤u,v≤n,u≠v)(1≤u,v≤n,u≠v), specifying a query that the starting point and ending point are the uuth and the vvth crossroads, respectively.
It is guaranteed that the sum of nn and the sum of qq over all test cases do not exceed 2.5×1052.5×105, and the sum of mm does not exceed 5×1055×105.
Output
For each query of each test case, print the answer in one line. If Acesrc might have nothing to eat, print 0; if there is no path between the given starting and ending point, print -1.