F. The Shortest Statementtime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given a weighed undirected connected graph, consisting of n vertices and m edges.You should answer q queries, the i-th query is to find the shortest distance between vertices u_i and v_i.InputThe first line contains two integers n and m~(1 \le n, m \le 10^5, m - n \le 20) — the number of vertices and edges in the graph.Next m lines contain the edges: the i-th edge is a triple of integers v_i, u_i, d_i~(1 \le u_i, v_i \le n, 1 \le d_i \le 10^9, u_i \neq v_i). This triple means that there is an edge between vertices u_i and v_i of weight d_i. It is guaranteed that graph contains no self-loops and multiple edges.The next line contains a single integer q~(1 \le q \le 10^5) — the number of queries.Each of the next q lines contains two integers u_i and v_i~(1 \le u_i, v_i \le n) — descriptions of the queries.Pay attention to the restriction m - n ~ \le ~ 20.OutputPrint q lines.The i-th line should contain the answer to the i-th query — the shortest distance between vertices u_i and v_i.ExamplesInput3 31 2 32 3 13 1 531 21 32 3Output341Input8 131 2 42 3 63 4 14 5 125 6 36 7 87 8 71 4 11 8 32 6 92 7 14 6 36 8 281 51 72 32 83 73 46 87 8Output75677127
Input3 31 2 32 3 13 1 531 21 32 3
Output341
['graphs', 'shortest paths', 'trees', '*2400']