B"You're given a simple, undirected, connected, weighted graph with n nodes and m edges. Nodes are numbered from 1 to n . There are exactly k centrals (recharge points), which are nodes 1, 2, ldots, k . We consider a robot moving into this graph, with a battery of capacity c , not fixed by the constructor yet. At any time, the battery contains an integer amount x of energy between 0 and c inclusive. Traversing an edge of weight w_i is possible only if x ge w_i , and costs w_i energy points ( x := x - w_i ). Moreover, when the robot reaches a central, its battery is entirely recharged ( x := c ). You're given q independent missions, the i -th mission requires to move the robot from central a_i to central b_i . For each mission, you should tell the minimum capacity required to acheive it. The first line contains four integers n , m , k and q ( 2 <= k <= n <= 10^5 and 1 <= m, q <= 3 cdot 10^5 ). The i -th of the next m lines contains three integers u_i , v_i and w_i ( 1 <= u_i, v_i <= n , u_i neq v_i , 1 <= w_i <= 10^9 ), that mean that there's an edge between nodes u and v , with a weight w_i . It is guaranteed that the given graph is simple (there is no self-loop, and there is at most one edge between every pair of nodes) and connected. The i -th of the next q lines contains two integers a_i and b_i ( 1 <= a_i, b_i <= k , a_i neq b_i ). You have to output q lines, where the i -th line contains a single integer : the minimum capacity required to acheive the i -th mission. In the first example, the graph is the chain 10 - 9 - 2^C - 4 - 1^C - 5 - 7 - 3^C - 8 - 6 , where centrals are nodes 1 , 2 and 3 . For the mission (2, 3) , there is only one simple path possible. Here is a simulat"...