// 找环问题：考虑floyd
// 枚举编号最大的点，然后枚举跟它相邻的两个点 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 505;
typedef long long LL;
const LL mod = 998244353;
const LL INF = 1e17;
int T, n, m;
vector< int > in[N], out[N];
LL f[N][N], g[N][N], mp[N][N];
int main() {
	scanf("%d", &T);
	while(T -- ) {
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; i ++ ) {
			vector< int > tmp; swap(tmp, in[i]);
			vector< int > gg; swap(gg, out[i]);
		}
		LL res = 1e18, ans = 0;
		for(int i = 1; i <= n; i ++ ) {
			for(int j = 1; j <= n; j ++ ) {
				f[i][j] = INF;
				g[i][j] = 0;
				mp[i][j] = INF;
			//	if(i == j) f[i][j] = 0;
			}
		}
		for(int i = 1; i <= m; i ++ ) {
			LL w;
			int u, v; scanf("%d%d%lld", &u, &v, &w);
			f[u][v] = min(f[u][v], w);
			g[u][v] = 1LL;
			mp[u][v] = w;
			in[v].pb(u); out[u].pb(v);
		}
		for(int i = 1; i <= n; i ++ ) {
			for(int j = 1; j <= n; j ++ ) {
				for(int k = 1; k <= n; k ++ ) {
					if(f[j][i] + f[i][k] < f[j][k]) {
						f[j][k] = f[j][i] + f[i][k];
						g[j][k] = 1;
					}
					else if(f[j][i] + f[i][k] == f[j][k]) {
						g[j][k] = (g[j][k] + g[j][i] * g[i][k] % mod) % mod;
					}
				}
			}
			for(auto v : in[i]) {
				for(auto k : out[i]) {
					if(v < i && k < i) {
						if(mp[v][i] + mp[i][k] + f[k][v] < res) {
							res = mp[v][i] + mp[i][k] + f[k][v];
							ans = 1;
						}
						else if(mp[v][i] + mp[i][k] + f[k][v] == res) {
							ans = (ans + g[k][v]) % mod;
						}
					}
				}
			}
		}
		if(res > 1e12) puts("-1 -1");
		else cout << res << ' ' << ans << endl;
	}
	return 0;
} 
/*
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
*/