找环

Problem Description

给定一张 $n$ 个点 $m$ 条边的有向图，可能有重边，也可能有自环。点的编号依次为 $1$ 到 $n$；第 $i$ 条边 $u_i\rightarrow v_i$ 的长度为 $998\,244\,353^{w_i}$。 请写一个程序，在给定的图中找到一个环，使得环上所有边的平均长度最小，或判断无解。

Input

第一行包含一个正整数 $T$ ($1\leq T\leq 100$)，表示测试数据的组数。 每组数据第一行包含两个正整数 $n,m$ ($1\leq n\leq 1000$, $1\leq m\leq 2000$)，分别表示点数和边数。 接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$ ($1\leq u_i,v_i\leq n$, $0\leq w_i < n$)，表示边 $u_i\rightarrow v_i$ 的长度为 $998\,244\,353^{w_i}$。 输入数据保证最多只有 $10$ 组数据满足 $n > 100$ 或 $m > 100$。

Output

对于每组数据输出一行：若找不到环，输出 ''$\texttt{-1}$''，否则假设答案是 $\frac{p}{q}$，你需要输出最小的非负整数 $r$ 满足 $q \cdot r \equiv p \pmod{(10^9+7)}$。你可以认为这样的 $r$ 一定存在。

Sample Input

6
3 3
1 2 0
2 3 0
3 1 0
2 1
1 2 0
2 2
1 2 0
2 1 1
3 5
1 2 0
1 3 1
2 3 2
3 2 0
2 3 1
4 5
1 2 3
2 3 3
3 1 3
2 4 1
4 1 1
1 1
1 1 0

Sample Output

1
-1
499122177
499122177
540815376
1

Source

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