#P18745. [正睿NOI2021训练] 最小割

[正睿NOI2021训练] 最小割

最小割

串并联图是一张带有源、汇的带权无向图,可以按以下规则构造:

  1. 一条边,以它的两个端点为源、汇。
  2. 串联两个串并联图:将第一个图的汇与第二个图的源合并,保留第一个图的源和第二个图的汇。
  3. 并联两个串并联图:合并两个图的源,再合并两个图的汇。

给定一张 nn 个点、mm 条边的带权无向图,保证存在两个点作为源、汇,可以将整张图视为上述串并联图。源、汇不直接给出。图中可以有重边,没有自环。

有 qq 次询问,每次给出 s,ts,t,求将 s,ts,t 分到割的两侧时,跨越割的所有边的权值之和的最小值。特别保证,每次询问的 s,ts,t 在原图中有直接相连的边。

输入格式

第一行三个整数 n,m,qn,m,q。

接下来 mm 行,每行三个整数 u,v,wu,v,w,表示一条权值为 ww 的无向边。

接下来 qq 行,每行两个整数 s,ts,t,表示询问。

输出格式

输出 qq 行,每行一个整数,表示对应的最小割权值。

数据范围

2≤n≤5×1052\le n\le5\times10^5,1≤m,q≤5×1051\le m,q\le5\times10^5,1≤u,v,s,t≤n1\le u,v,s,t\le n,u≠vu\ne v,s≠ts\ne t,1≤w≤1091\le w\le10^9。答案需要 64 位整数。

样例 1

输入

3 3 3
1 2 1
2 3 2
1 3 3
1 2
1 3
2 3

输出

3

4

3