#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct Edge {
int u, v;
long long w;
bool operator<(const Edge& o) const {
return w < o.w;
}
};
struct Query {
int l, r, id;
};
const int MAXN = 100005;
int parent_dsu[MAXN];
int find_set(int v) {
if (v == parent_dsu[v]) return v;
return parent_dsu[v] = find_set(parent_dsu[v]);
}
vector<pair<int, long long>> adj[MAXN];
long long dist_root[MAXN];
int tin[MAXN], timer_tin = 0;
int euler[2 * MAXN], euler_depth[2 * MAXN], first_occ[MAXN], timer_euler = 0;
void dfs(int u, int p, int d, long long current_dist) {
tin[u] = timer_tin++;
dist_root[u] = current_dist;
first_occ[u] = timer_euler;
euler[timer_euler] = u;
euler_depth[timer_euler] = d;
timer_euler++;
for (auto& edge : adj[u]) {
int v = edge.first;
long long w = edge.second;
if (v != p) {
dfs(v, u, d + 1, current_dist + w);
euler[timer_euler] = u;
euler_depth[timer_euler] = d;
timer_euler++;
}
}
}
int st[20][2 * MAXN];
int lg[2 * MAXN];
void build_rmq() {
lg[1] = 0;
for (int i = 2; i <= timer_euler; i++) lg[i] = lg[i / 2] + 1;
for (int i = 0; i < timer_euler; i++) st[0][i] = i;
for (int j = 1; (1 << j) <= timer_euler; j++) {
for (int i = 0; i + (1 << j) <= timer_euler; i++) {
int left = st[j - 1][i];
int right = st[j - 1][i + (1 << (j - 1))];
st[j][i] = (euler_depth[left] < euler_depth[right]) ? left : right;
}
}
}
int get_lca(int u, int v) {
int l = first_occ[u];
int r = first_occ[v];
if (l > r) swap(l, r);
int j = lg[r - l + 1];
int left = st[j][l];
int right = st[j][r - (1 << j) + 1];
return (euler_depth[left] < euler_depth[right]) ? euler[left] : euler[right];
}
long long get_dist(int u, int v) {
return dist_root[u] + dist_root[v] - 2 * dist_root[get_lca(u, v)];
}
struct DLLNode {
int prev, next;
} dll[MAXN];
long long current_VT_weight2 = 0;
struct State {
int u;
long long old_weight;
};
vector<State> history;
void delete_node(int u, bool save) {
if (save) history.push_back({u, current_VT_weight2});
int p = dll[u].prev;
int n = dll[u].next;
if (p != u) {
current_VT_weight2 -= get_dist(p, u);
current_VT_weight2 -= get_dist(u, n);
current_VT_weight2 += get_dist(p, n);
dll[p].next = n;
dll[n].prev = p;
} else {
current_VT_weight2 = 0;
}
}
void undo() {
State s = history.back();
history.pop_back();
int u = s.u;
current_VT_weight2 = s.old_weight;
int p = dll[u].prev;
int n = dll[u].next;
if (p != u) {
dll[p].next = u;
dll[n].prev = u;
}
}
long long solve_small(int l, int r) {
if (l == r) return 0;
vector<int> nodes;
for (int i = l; i <= r; i++) nodes.push_back(i);
sort(nodes.begin(), nodes.end(), [](int a, int b) {
return tin[a] < tin[b];
});
long long wt2 = 0;
int k = nodes.size();
for (int i = 0; i < k; i++) {
wt2 += get_dist(nodes[i], nodes[(i + 1) % k]);
}
return wt2 / 2;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, Q;
if (!(cin >> N >> M >> Q)) return 0;
vector<Edge> edges(M);
for (int i = 0; i < M; i++) {
cin >> edges[i].u >> edges[i].v >> edges[i].w;
}
sort(edges.begin(), edges.end());
for (int i = 0; i < N; i++) parent_dsu[i] = i;
long long W_MST = 0;
for (int i = 0; i < M; i++) {
int pu = find_set(edges[i].u);
int pv = find_set(edges[i].v);
if (pu != pv) {
parent_dsu[pu] = pv;
adj[edges[i].u].push_back({edges[i].v, edges[i].w});
adj[edges[i].v].push_back({edges[i].u, edges[i].w});
W_MST += edges[i].w;
}
}
dfs(0, -1, 0, 0);
build_rmq();
vector<int> global_order(N);
for (int i = 0; i < N; i++) global_order[i] = i;
sort(global_order.begin(), global_order.end(), [](int a, int b) {
return tin[a] < tin[b];
});
vector<Query> queries(Q);
for (int i = 0; i < Q; i++) {
cin >> queries[i].l >> queries[i].r;
queries[i].id = i;
}
int B = max(1, (int)(N / sqrt(Q)));
vector<Query> diff_block_queries;
vector<long long> ans(Q);
for (int i = 0; i < Q; i++) {
if (queries[i].l / B == queries[i].r / B) {
ans[queries[i].id] = W_MST - solve_small(queries[i].l, queries[i].r);
} else {
diff_block_queries.push_back(queries[i]);
}
}
sort(diff_block_queries.begin(), diff_block_queries.end(), [&](const Query& a, const Query& b) {
int ba = a.l / B;
int bb = b.l / B;
if (ba != bb) return ba < bb;
return a.r > b.r;
});
int num_blocks = (N / B) + 1;
int q_idx = 0;
int num_diff = diff_block_queries.size();
for (int b = 0; b < num_blocks && q_idx < num_diff; b++) {
if (diff_block_queries[q_idx].l / B != b) continue;
int block_start = b * B;
vector<int> nodes_in_suffix;
for (int i = 0; i < N; i++) {
if (global_order[i] >= block_start) {
nodes_in_suffix.push_back(global_order[i]);
}
}
int V = nodes_in_suffix.size();
current_VT_weight2 = 0;
if (V > 0) {
for (int i = 0; i < V; i++) {
int u = nodes_in_suffix[i];
int nxt = nodes_in_suffix[(i + 1) % V];
int prv = nodes_in_suffix[(i - 1 + V) % V];
dll[u].next = nxt;
dll[u].prev = prv;
current_VT_weight2 += get_dist(u, nxt);
}
}
int curr_R = N - 1;
while (q_idx < num_diff && diff_block_queries[q_idx].l / B == b) {
int L = diff_block_queries[q_idx].l;
int R = diff_block_queries[q_idx].r;
int id = diff_block_queries[q_idx].id;
while (curr_R > R) {
delete_node(curr_R, false);
curr_R--;
}
int saves = 0;
for (int x = block_start; x < L; x++) {
delete_node(x, true);
saves++;
}
ans[id] = W_MST - current_VT_weight2 / 2;
for (int i = 0; i < saves; i++) {
undo();
}
q_idx++;
}
}
for (int i = 0; i < Q; i++) cout << ans[i] << "\n";
return 0;
}
