Circuit

Problem Description

Now there is a directed graph $G=(V,E)$ with $n$ vertices and $m$ edges (the graph does not guarantee connectivity). You need to calculate the length of the circuit with the smallest length. At the same time, on this basis you also need to count the number of the circuit with the smallest length. There are no multiedges and self-loops in the graph.

Input

The first line of input is a positive integer $T(T \leq 15)$ representing the number of test cases. Description of the test cases follows: The first line of each test case contains two integers $n$ and $m$ $(1\leq n\leq 500, 0\leq m\leq n\times(n-1))$—— the number of the vertices and edges in the given graph. Each of the next $m$ lines contains two integers $u_i$ , $v_i$ and $w_i$ $(1\leq u_i,v_i\leq n,1\leq w_i\leq 10^9)$meaning that there is a directed edge of length $w_i$ between vertex $u_i$ and vertex $v_i$ in the graph. The data guarantees that there will be no more than $10$ groups with a value of $n$ exceeding $100$.

Output

For each case, output two integers representing the length and the number of the circuit with the smallest length. Since the number may be large, you need to output the result of modulating the answer to $998244353$.Output -1 -1 if there is no circuit.

Sample Input

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

Sample Output

7 2
-1 -1
8 4

Source

2023“钉耙编程”中国大学生算法设计超级联赛（4）