CF1051F The Shortest Statement

You 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 $ .

The 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 $ .

Print $ 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 $ .