题目描述

给一个 $n$ 个点，$m$ 条边的无向图，边有边权 $w_i$.

$Q$ 次询问，每次给出一个点集 $V$ ,询问 $\sum_{u\in V,v\in V,u\ne v}\text{MinCut}^2(u,v)$ ，其中 $\text{MinCut}(u,v)$ 表示原图上 $u,v$ 的最小割（若 $u,v$ 不连通则为 $0$）。

输入格式

第一行两个正整数 $n,m$。

接下来 $m$ 行，每行三个正整数 $u,v,w$，表示一条连接 $u,v$，权值为 $w$ 的无向边。

接下来一个正整数 $Q$。

接下来 $Q$ 行，每行先是一个正整数 $k\ (k\ge 2)$ 表示点集大小，接下来 $k$ 个数描述了这个点集（保证以升序给出）。

输出格式

对每个询问，输出一个整数 $ans$ 表示答案。

4 6
2 1 8
4 2 3
2 3 1
3 3 8
2 4 9
4 1 8
3
3 1 2 3
4 1 2 3 4
2 2 4

516
1830
800

第一组询问的点集是 $\{1,2,3\}$。其中 $1,2$ 的最小割为 $16$；$1,3$ 的最小割为 $1$；$2,3$ 的最小割也是 $1$。故答案为 $16^2+1^2+16^2+1^2+1^2+1^2=516$。

6 15
6 2 10
5 1 2
5 3 7
6 6 4
1 3 2
4 6 7
6 1 3
2 4 4
4 3 4
1 5 6
6 4 1
5 3 10
3 3 10
3 2 7
2 3 4
5
3 2 5 6 
6 1 2 3 4 5 6 
3 2 3 6 
3 3 4 6 
3 1 2 5 

2178
8180
2178
1672
1324

数据范围与提示

对 $30\%$ 的数据，$n\le 100,m\le 300,Q\le 50$.
对 $50\%$ 的数据，$n\le 200,m\le 400,Q\le 200$
对 $100\%$ 的数据，$n\le 400,m\le 800,Q\le 1.5\times 10^4$