Farmer John 一直在当地大学上夜间算法课，刚学到了最小生成树。不过，他意识到农场设计还不够高效，想简化农场的布局。

现在农场像一张图：顶点代表田地，边代表田地间的小路，每条都有长度。Farmer John 注意到，每种长度最多有三条小路。FJ 想删除一些小路，让农场成为树，即任意两块田地之间恰好有一条路线。他还希望这是一棵最小生成树，即边长总和尽可能小的树。

请帮 Farmer John 不仅计算农场图的最小生成树边长总和，还要计算他能创建多少棵不同的最小生成树。

输入格式

• 第 $1$ 行：两个整数 $N$ 和 $M$，$1 \le N \le 40,000; 1 \le M \le 100,000$，分别表示农场图的顶点数和边数。顶点编号为 $1\ldots N$。
• 第 $2\ldots M+1$ 行：三个整数 $a_{i}$、$b_{i}$ 和 $n_{i}$，$1 \le a_{i}, b_{i} \le N; 1 \le n_{i} \le 1,000,000$，表示从顶点 $a_{i}$ 到 $b_{i}$、长度为 $n_{i}$ 的一条边。同一边长 $n_{i}$ 不会出现超过三次。

输出格式

• 第 $1$ 行：两个整数，表示最小生成树长度和最小生成树数量（对 $1,000,000,007$ 取模）。

样例

输入格式 1

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

输出格式 1

4 3

说明

选择两条长度为 $1$ 的边以及任意一条长度为 $2$ 的边，就得到长度为 $4$ 的最小生成树。

题目作者：Nathan Pinsker，2011