#include<bits/stdc++.h>
#define irep(i,l,r) for(int i = l; i <= r; ++i)
#define drep(i,r,l) for(int i = r; i >= l; --i)
#define ceil(pp,qq) (((pp)>0)^((qq)>0)?-Abs(pp)/Abs(qq):(pp)%(qq)?(pp)/(qq)+1:(pp)/(qq))
#define floor(pp,qq) (((pp)>0)^((qq)>0)?-ceil(abs(pp),abs(qq)):(pp)/(qq))
#define ll long long
using namespace std;
ll Abs(ll x){return x > 0 ? x : - x;}
inline ll read(){
	char ch = getchar();
	ll s = 0;
	while(!isdigit(ch)){ch = getchar();}
	while(isdigit(ch))s = (s << 3) + (s << 1) + (ch ^ 48), ch = getchar();
	return s;
}

const ll itinf = 2e9;
const ll llinf = 4e18;
const ll mod = 1000000007;
const ll N = 584;//500009;
ll dis[N][N], cnt[N][N];
void solve(){
	ll n = read(), m = read();
	memset(dis, 0x0f, sizeof(dis));
	memset(cnt, 0, sizeof(cnt));
	vector<array<ll,3>>edge;
	vector<ll>g[507];
	ll inf = dis[0][0];
	irep(i,0,n)dis[i][i] = 0, cnt[i][i] = 0;
	irep(i,0,m - 1){
		ll u = read(), v = read(), w = read();
		cnt[u][v] = 1, dis[u][v] = w;
		edge.push_back({u,v,w});
		g[u].push_back(i);
	}
	
	ll minans = inf, ans = 0;
	irep(k,1,n){
		irep(i,1,n){
			irep(j,1,n){
				if(dis[i][j] > dis[i][k] + dis[k][j]){
					dis[i][j] = dis[i][k] + dis[k][j];
					cnt[i][j] = cnt[i][k] * cnt[k][j];
				}
				else if(dis[i][j] == dis[i][k] + dis[k][j]){
					cnt[i][j] += cnt[i][k] * cnt[k][j];
				}
			}
		}
		for(ll uu : g[k]){
			auto [u,v,w] = edge[uu];
			if(v > k)continue;
			if(w + dis[v][u] < minans){
				minans = w + dis[v][u];
				ans = cnt[v][u];	
			}
			else if(w + dis[v][u] == minans){
				ans += cnt[v][u];
			}
		}
		if(m == 249500 && minans == 500){
			cout << ans << endl;
		}
	}
	
	if(minans == inf)puts("-1 -1");
	else cout << (long long)minans << ' ' << (long long)ans << endl;
}

int main(){
	int T = read();
	while(T --){
		solve();
	}
	return 0;
}