408563: GYM103186 F 鸡哥的限币令

众所周知，鸡哥炒币亏了很多钱，他的钱大部分都被无良庄家骗走了。那么，打不过就加入，鸡哥也决定下海成为一个庄家。于是机智的鸡哥决定开一个炒币平台，取名"鸡币"。

在鸡币平台中，有 $$$n$$$ 个商家，编号为 $$$1$$$ 到 $$$n$$$。商家之间存在 $$$m$$$ 个单向的供货关系，编号为 $$$1$$$ 到 $$$m$$$ 。一条 $$$u \rightarrow v$$$ 权值为 $$$w$$$ 的边代表商家 $$$u$$$ 向商家 $$$v$$$ 卖 $$$w$$$ 的虚拟货币。

但好景不长，鸡哥才小赚没几天，就出现了问题。原来是鸡哥的服务器是土豆做的，无法承受这么多交易。为了减轻服务器的压力，鸡哥决定出台限币令限制一些供货关系，使虚拟货币的交易总额尽可能小，但不能没有交易让鸡哥白白运维服务器亏钱。

鸡哥立志建立良好币圈生态，同时还能每天小赚到一点。而有些商家只卖不买，有些商家只买不卖，就会造成了市场的不平衡。于是，鸡哥又在限币令中加了一条规定：每个商家对于与其他商家的买和卖的供货关系至少各存在一组。

请你帮帮鸡哥选出一组满足上述要求的最好的商家供货关系，使得它们的交易总额最小。鸡哥会报答你的。

第一行有两个整数 $$$n, m$$$ ($$$2 \leq n \leq 300$$$, $$$1 \leq m \leq n \cdot (n - 1)$$$)，分别表示鸡币平台商家数量和商家之间供货关系数量。

接下来 $$$m$$$ 行，每行三个整数 $$$u, v, w$$$，表示商家 $$$u$$$ 向商家 $$$v$$$ 卖 $$$w$$$ 的虚拟货币。 ($$$1 \leq u, v \leq n$$$,$$$ u \neq v$$$, $$$1 \leq w \leq 10 ^ 5$$$)。保证从 $$$u$$$ 向 $$$v$$$ 的供货关系最多只会有一条。

如果鸡哥能成功出台限币令，在第一行输出一个整数 $$$w$$$，表示总的最少交易额。

第二行输出一个整数 $$$k$$$，表示鸡哥限币令下仍然开放的供货关系，接着输出 $$$k$$$ 个整数，$$$a_1, a_2, \ldots a_k$$$，分别表示鸡哥认可的供货关系的编号，中间用空格分隔。如果有多种符合条件的方式，输出任意一种即可。

如果鸡哥不能找到一组满足他要求的供货关系，则输出一行 $$$-1$$$。

3 5
1 2 1
2 1 2
1 3 3
3 1 4
3 2 5

10
3 2 3 5

3 3
1 2 1
2 3 1
1 3 1

-1