#include<bits/stdc++.h>
using namespace std;
int n,m;
int wi[510][510];
const int I=1e9+10,mod=998244353;
#define ll long long
const ll I2=1e18;
ll dis[510];
int fh[510];
bool vis[510];
void ad(int &x,int y){x+=y;if(x>=mod)x-=mod;}
void sol(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)wi[i][j]=I;
    for(int i=1,u,v,w;i<=m;i++)
    scanf("%d%d%d",&u,&v,&w),wi[u][v]=w;
    ll ans=1e18;int ans2=0;
    for(int s=1;s<n;s++){
        for(int i=1;i<=n;i++)dis[i]=1e18,fh[i]=0,vis[i]=0;
        dis[s]=0,fh[s]=1;
        for(int st=1;st<=n-s+1;st++){
            int u=-1;
            for(int i=s;i<=n;i++)if(!vis[i]&&(u==-1||dis[u]>dis[i]))u=i;
            if(dis[u]>=I2)continue;
            vis[u]=1;
            for(int i=s;i<=n;i++)if(wi[u][i]!=I){
                if(dis[i]>dis[u]+wi[u][i])
                dis[i]=dis[u]+wi[u][i],fh[i]=fh[u];
                else if(dis[i]==dis[u]+wi[u][i])
                ad(fh[i],fh[u]);
            }
        }
        for(int i=s+1;i<=n;i++)if(wi[i][s]!=I&&dis[i]<I2){
            if(dis[i]+wi[i][s]<ans)
            ans=dis[i]+wi[i][s],ans2=fh[i];
            else if(dis[i]+wi[i][s]==ans)
            ad(ans2,fh[i]);
        }
    }
    if(ans==I2)puts("-1 -1");
    else printf("%lld %d\n",ans,ans2);
}
int main(){
    int T;scanf("%d",&T);while(T--)sol();
    return 0;
}