{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cpre\u003e\u003ch2\u003eDescription\u003c/h2\u003e\n\nOnce again, James Bond is on his way to saving the world. Bond\u0027s latest mission requires \nhim to travel between several pairs of cities in a certain country.\n\nThe country has N cities (numbered by 1, 2, . . ., N), connected by M bidirectional roads. \nBond is going to steal a vehicle, and drive along the roads from city s to city t. \nThe country\u0027s police will be patrolling the roads, looking for Bond, however, not all \nroads get the same degree of attention from the police.\n\nMore formally, for each road MI6 has estimated its dangerousness, the higher it is, \nthe more likely Bond is going to be caught while driving on this road. Dangerousness \nof a path from s to t is defined as the maximum dangerousness of any road on this path.\n\nNow, it\u0027s your job to help Bond succeed in saving the world by finding the least dangerous \npaths for his mission.\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\nThere will be at most 5 cases in the input file.\n\nThe first line of each case contains two integers N, M (2 ≤ N≤ 50000, 1≤ M ≤ 100000) – \nnumber of cities and roads. The next M lines describe the roads. The i-th of these lines \ncontains three integers: xi, yi, di (1 ≤ xi, yi ≤ N, 0 ≤ di ≤ 10^9) - the numbers of the \ncities connected by the ith road and its dangerousness.\n\nDescription of the roads is followed by a line containing an integer Q (1 ≤ Q ≤ 50000), followed \nby Q lines, the i-th of which contains two integers si and ti (1 ≤ si, ti ≤ N, si !\u003d ti). \n\nConsecutive input sets are separated by a blank line.\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\nFor each case, output Q lines, the i-th of which contains the minimum dangerousness of a path \nbetween cities si and ti. Consecutive output blocks are separated by a blank line.\n\nThe input file will be such that there will always be at least one valid path.\n\n\u003ch2\u003eSample Input\u003c/h2\u003e\n\n4 5\n1 2 10\n1 3 20\n1 4 100\n2 4 30\n3 4 10\n2\n1 4\n4 1\n\n2 1\n1 2 100\n1\n1 2\n\n\u003ch2\u003eSample Output\u003c/h2\u003e\n\n20\n20\n\n100\n\n\u003ch2\u003eSource\u003c/h2\u003e\n\nIvan Krasilnikov @ Next generation contest – 4 @ UVA\n\n\u003c/pre\u003e"}}]}