Every respectable contest must have a textbook graph problem. No convoluted processes, no weird observations; just pure, raw algorithmics. Lucky for you, you've just found it!

The picture above depicts the example test case.
You are given an undirected, weighted graph with vertices and edges, as well as queries of form (a_i, b_i). For each of the queries, find the length of the shortest path between vertices a_i and b_i.
The input consists of m + q + 1 lines. The first line of the input will contain three integers , , and (1 \leq n \leq 100\:000, 1 \leq m \leq 200\:000, 1 \leq q \leq 25\:000). Each of the next lines contain three integers u_i, v_i, and w_i, denoting undirected edge between vertices u_i and v_i of length w_i (1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9). Finally, each of the last lines contain two integers a_i, b_i (1 \leq a_i, b_i \leq n).
There is at most one edge between any pair of vertices, and no edges that connect a vertex with itself.
Moreover, it is guaranteed that all edges u_i, v_i satisfy |u_i - v_i| \leq 10.
Output lines. The -th line should contain a single positive integer, representing the minimum length of a path that connects the vertices in the -th query. If there is no such path, output for that specific query.
Example 1