Chiaki 擅长生成特殊的图。最初，她有一个仅包含两个顶点且由一条边连接的图。每次操作时，她可以选择一条边 $(u, v)$，将其复制一份，并在该边中插入一些新的顶点（可能为零个，即设新顶点为 $t_1, t_2, \dots, t_k$，Chiaki 会在图中插入边 $(u, t_1), (t_1, t_2), \dots, (t_{k-1}, t_k), (t_k, v)$）。

给定一个由上述操作生成的带权图，Chiaki 想知道该图的最大权匹配的权值之和，以及不同最大权匹配的数量（对 $10^9 + 7$ 取模）。

图中的匹配是指一组两两不相邻的边，且其中没有环；也就是说，没有两条边共享同一个顶点。

最大权匹配定义为权值之和最大的匹配。

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示顶点数和边数。

接下来 $m$ 行，每行包含三个整数 $u_i, v_i$ 和 $w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le 10^9$)，表示连接 $u_i$ 和 $v_i$ 的一条权值为 $w_i$ 的边。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $10^6$。

对于每组测试数据，输出两个由空格分隔的整数。第一个整数是最大权匹配的权值之和，第二个整数是不同最大权匹配的数量对 $10^9 + 7$ 取模的结果。

样例

输入 1

2
6 7
1 2 1
2 3 1
4 5 1
5 6 1
1 4 1
2 5 1
3 6 1
4 5
1 2 1
1 3 1
1 4 1
2 3 1
3 4 1

输出 1

3 3
2 2