#9313. 「USACO11DEC」 Simplifying the Farm G 省选/NOI−

农夫约翰在当地大学上了一门夜间算法课程，他刚刚学会了最小生成树。

约翰现在意识到他的农场的设计并没有尽可能的高效，因此他想简化农场的布局。

农场的结构可以用一个图来表示。

图的顶点代表田地，边代表田地之间的道路，每条道路都有一定的长度。

约翰注意到，对于每个不同的长度，最多有三条边的边长等于该长度。

约翰希望删除其中的一些道路，让整个图形变为一棵树。

也就是说，在任何田地之间都存在一条唯一的连通路径。

此外，约翰希望这是一棵最小生成树——一棵具有最小边长和的树。

请帮助约翰计算从他的农场图可以得到的最小生成树的边长之和以及他可以得到的不同最小生成树的数量。

第一行包含两个整数 和 ，分别表示农场图中点和边的数量，所有点的编号从 到 。

接下来 行，每行包含三个整数 ，表示点 和 之间存在一条边，边长为 。

没有任何边长 会出现超过三次。

共一行，首先输出最小生成树的边长之和，然后输出最小生成树的数量对 取模后的结果。

输入样例：

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

输出样例：

4 3

样例解释

去掉两条边长为 的边以及任何一条边长为 的边，就可以获得最小生成树。

最小生成树的边长之和为 。

,
,
,