?𝐵B?頭奶牛?(1≤𝐵≤25000)(1≤B≤25000)，有?𝑁(2×𝐵≤𝑁≤50000)N(2×B≤N≤50000)?個農場，編號?11?到?𝑁N，有?𝑀(𝑁?1≤𝑀≤100000)M(N?1≤M≤100000)?條雙向邊，第?𝑖i?條邊連接農場?𝑅𝑖Ri??和?𝑆𝑖(1≤𝑅𝑖≤𝑁,1≤𝑆𝑖≤𝑁)Si?(1≤Ri?≤N,1≤Si?≤N)，該邊的長度是?𝐿𝑖(1≤𝐿𝑖≤2000)Li?(1≤Li?≤2000)。居住在農場?𝑃𝑖Pi??的奶牛 A?(1≤𝑃𝑖≤𝑁)(1≤Pi?≤N)，想送一份新年禮物給居住在農場?𝑄𝑖(1≤𝑄𝑖≤𝑁)Qi?(1≤Qi?≤N)?的奶牛 B，但是奶牛 A 必須先到大衛老師（居住在編號?11?的農場）那里取禮物，然后再送給奶牛 B。你的任務是：奶牛 A 至少需要走多遠的路程？

輸入格式

• 第一行三個整數?𝑁,𝑀,𝐵N,M,B。

• 第?22?至?𝑀+1M+1?行，每行?33?個整數?𝑅𝑖,𝑆𝑖,𝐿𝑖Ri?,Si?,Li?。

• 第?𝑀+2M+2?至?𝑀+𝐵+1M+B+1?行，進行?𝐵B?次詢問，每行?22?個整數?𝑃𝑖,𝑄𝑖Pi?,Qi?。

輸出格式

每次詢問輸出一個整數，即答案。

輸入輸出樣例

輸入 #1復制

6 7 3 
1 2 3 
5 4 3 
3 1 1 
6 1 9 
3 4 2 
1 4 4 
3 2 2 
2 4 
5 1 
3 6 

輸出 #1復制

6 
6 
10 

代碼：

#include<bits/stdc++.h>
using namespace std;
struct Edge {int to;int weight;
};
class Graph {
public:int sum;  // 農場的數量vector<vector<Edge>> ve;  // 鄰接表Graph(int n) {sum = n;ve.resize(n + 1);}void addEdge(int from, int to, int weight) {ve[from].push_back({to, weight});ve[to].push_back({from, weight});}int a(int start, int target) {vector<int> distance(sum + 1, INT_MAX);vector<bool> visited(sum + 1, false);distance[start] = 0;priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;pq.push({0, start});while (!pq.empty()) {int u = pq.top().second;pq.pop();if (visited[u]) {continue;}visited[u] = true;for (const auto& edge : ve[u]) {int v = edge.to;int weight = edge.weight;if (distance[u] + weight < distance[v]) {distance[v] = distance[u] + weight;pq.push({distance[v], v});}}}return distance[target];}
};int main() {int N, M, B;cin >> N >> M >> B;Graph graph(N);for (int i = 0; i < M; ++i) {int R, S, L;cin >> R >> S >> L;graph.addEdge(R, S, L);}for (int i = 0; i < B; ++i) {int P, Q;cin >> P >> Q;int dn = graph.a(P, 1) + graph.a(1, Q);cout << dn << endl;}return 0;
}