#include <stdio.h>

#include <iostream>

#include <vector>

#include <math.h>

#include <algorithm>

#include <string.h>

#include <string>

using namespace std;

typedef long long LL;

const int N=1e2+;

const int INF=5e8;

int mp[N][N],dis[N][N];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--){

      int n,m;

      scanf("%d%d",&n,&m);

      for(int i=;i<=n;++i)

        for(int j=;j<=n;++j)

          mp[i][j]=INF;

      for(int i=;i<m;++i){

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        if(w<mp[u][v])

          mp[u][v]=mp[v][u]=w;

      }

      for(int i=;i<=n;++i)

        for(int j=;j<=n;++j)

          dis[i][j]=mp[i][j];

      int mx=INF,cnt=;

      for(int k=;k<=n;++k){

        for(int i=;i<k;++i)

          for(int j=i+;j<k;++j)

            if(mx>mp[i][k]+mp[j][k]+dis[i][j])

              mx=mp[i][k]+mp[j][k]+dis[i][j],cnt=;

            else if(mx==mp[i][k]+mp[j][k]+dis[i][j])++cnt;

        for(int i=;i<=n;++i)

          for(int j=;j<=n;++j)

            dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);

      }

      if(cnt==)printf("-1\n");

      else printf("%d %d\n",mx,cnt);

    }

    return ;

}