Shortest Path Sum
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

You are given a connected graph with vertices and undirected edges.
We define as the length of shortest path from to in the graph.
There are queries, each query given three integers . For each query, you should find a node with the minimum value of and output the minimum value.

输入描述:

The first line of the input contains two integers  and  — the number of vertices and queries.
Then lines follow, each line contains two integers , representing an undirected edge between vertices and .
Then lines follow, each line contains three integers , and , query the minimum value of .

输出描述:

The output has  lines, each line contains an integer, representing the answer of the query.
示例1

输入

复制
6 5
1 2
2 3
2 4
3 4
4 5
5 6
1 1 1
1 3 4
2 3 4
4 5 6
1 5 6

输出

复制
0
3
2
2
4