P3037 [USACO11DEC] Simplifying the Farm G

题目描述

农夫约翰在一所夜校学习算法课程，他刚刚学会了最小生成树。现在约翰意识到他的农场设计得不够高效，他想简化农场的布局。 约翰的农场可以看做一个图，农田代表图中顶点，田间小路代表图中的边，每条边有一定的长度。约翰注意到，农场中最多有三条小路有着相同的长度。约翰想删除一些小路使得农场成为一棵树，使得两块农田间只有一条路径。但是约翰想把农场设计成最小生成树，也就是农场道路的总长度最短。 请帮助约翰找出最小生成树的总长度，同时请计算出总共有多少种最小生成树？

输入格式

第 \(1\) 行：两个整数 \(N\) 和 \(M(1 \le N \le 4\times 10^4; 1 \le M \le 10^5)\)，分别表示农场图中顶点和边的数量。顶点编号为 \(1 \sim N\)。 第 \(2\) 行到第 \(M+1\) 行：每行三个整数 \(a_i, b_i\) 和 \(n_i(1 \le a_i, b_i \le N; 1 \le n_i \le 10^6)\)，表示一条从顶点 \(a_i\) 到顶点 \(b_i\)、长度为 \(n_i\) 的边。任何边长度值 \(n_i\) 最多出现三次。

输出格式

第 \(1\) 行：输出两个整数，分别表示最小生成树的总边长度和不同最小生成树的数量（结果对 \(10^9+7\) 取模）。

输入输出样例 #1

输入 #1

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

输出 #1

4 3

说明/提示

样例解释：

选择两条长度为 \(1\) 的边和任意一条长度为 \(2\) 的边，就能得到总长度为 \(4\) 的最小生成树。