题目描述

给定一张 $n$ 个点 $m$ 条边的有向图，可能有重边，也可能有自环。点的编号依次为 $1$ 到 $n$；第 $i$ 条边 $u_i→v_i$ 的长度为 $998244353^{w_i}$。

请写一个程序，在给定的图中找到一个环，使得环上所有边的平均长度最小，或判断无解。

输入格式

第一行包含一个正整数 $T$ ($1≤T≤100$)，表示测试数据的组数。

每组数据第一行包含两个正整数 $n,m$ ($1≤n≤1000, 1≤m≤2000$)，分别表示点数和边数。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$ ($1≤u_i,v_i≤n, 0≤w_i<n$)，表示边 $u_i→v_i$ 的长度为 $998244353^{w_i}$。

输入数据保证最多只有 $10$ 组数据满足 $n>100$ 或 $m>100$。

输出格式

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

输入样例

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

输出样例

1
-1
499122177
499122177
540815376
1