给定一个包含 $n$ 个顶点和 $m$ 条边的有向图 $G=(V, E)$（图不保证连通）。你需要计算图中长度最小的回路的长度。同时，在此基础上，你还需要统计长度最小的回路的数量。图中不存在重边和自环。

输入格式

输入的第一行是一个正整数 $T(T \le 15)$，表示测试用例的数量。 每个测试用例的描述如下： 每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 500, 0 \le m \le n \times (n - 1)$)，分别表示给定图中的顶点数和边数。 接下来的 $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$ 超过 $100$ 的测试用例组数不超过 $10$ 组。

输出格式

对于每个测试用例，输出两个整数，分别表示长度最小的回路的长度和数量。由于数量可能很大，你需要将数量对 $998244353$ 取模后输出。如果不存在回路，则输出 -1 -1。

样例

样例输入 1

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

样例输出 1

7 2
-1 -1
8 4