F-最便宜的构建_牛客小白月赛74

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

有一天，牛牛获得了一张 $n$ 个结点 $m$ 条边的无向连通图，其中每条边都有边权，第 $i$ 条边的边权记为 $w_i$ 。

牛妹想考一考牛牛，她选择了 $k$ 个关于结点的集合，第 $i$ 个集合中有 $s_i$ 个结点编号，这 $s_i$ 个结点编号分别记为： $q_{i,1},q_{i,2},...,q_{i,s_i}$ 。

牛妹让牛牛在图的 $m$ 条边中选择一个子集构成一个子图，使得牛妹选择的 $k$ 个集合都被【满足】，一个集合被【满足】当且仅当集合中结点编号所代表的结点在子图上是连通的。

显然能够使得 $k$ 个集合都被【满足】的边集选择方案可能不止一个，所以牛牛想问你所有可能的边集选择方案中，被选择边中边权最大的那条边最少得是多少？

第一行输入两个空格分隔的整数 $n\ m$ 。

接下来 $m$ 行，第 i 行输入三个空格分隔的整数： $u\ v\ w_i$ ，代表图中存在一条连接了 $u$ 和 $v$ 边权为 $w_i$ 的边。

接下来输入一行一个整数代表 $k$ 。

接下来 $k$ 行，第 $i$ 行输入若干个空格分隔的整数： $s_i, q_{i,1},q_{i,2},...,q_{i,s_i}$ ，描述了牛妹选择的第 $i$ 个集合。

保证：

$1 \leq n,m \le 10^5$

$1 \leq u,v,k,q_{i,j} \le n$

$1 < s_i\le n$

$0 < w_i \le 10^9$

牛妹选择的 $k$ 个集合中结点个数的和不超过 $2\times 10^5$ ，且同一个集合中不会出现重复的结点。图中无重边，无自环。

一行一个整数代表所有符合牛妹要求的边集选择方案中边权最大的那条边最少是多少。

示例1

复制

复制

选择输入的第 1，4，5 条边即可，其中边权最大为 4。