//412_4
#include <iostream>
#include <algorithm>
#include <stdio.h>
using namespace std;

const int N = 2e3+3;
const int M = 6e3+3;

int eb[N], es[M], e[M], ec[M], ed;
void adde(int i, int j, int l){
    ++ed;
    e[ed] = j;
    ec[ed] = l;
    es[ed] = eb[i];
    eb[i] = ed;
}


int K,D;
int c[N], d[N];
int b[N];
bool u[N];

int main()
{
    freopen("SOCHI.IN","r", stdin);
    //freopen("input.txt", "r", stdin);



    int tt;
    scanf("%d",&tt);
    while(tt--){
        int n,m;
        scanf("%d%d",&n,&m);

        ed = 0;
        for(int i=0;i<n;++i) eb[i] = 0;

        for(int k=0;k<m;++k){
            int i,j,l;
            scanf("%d%d%d",&i,&j,&l);
            --i; --j;
            adde(i,j,l);
            adde(j,i,l);

        }

        int ans = -1;

        for(int A = 0; A<n;++A){

            for(K = 1; (K+1)*(K+1)<=n; ++K);
            D = n/K + (n%K!=0);

            int inf  =1e9;
            for(int x=0;x<D;++x) b[x] = x*K;

            for(int i = 0; i<D; ++i)
            for(int k = 0; k<K; ++k){
                int x = i*K+k;
                c[x] = inf;
                d[x] = inf;
                u[x] = 0;
            }

            c[A] = d[A] = 0;
            b[A/K] = A;

           // printf("?%d %d %d\n",A,K,D);

            for(;;){
                int i  =-1;
                for(int j=0;j<D;++j) if((i==-1 || c[b[j]]<c[i])) i = b[j];
                if(i==-1 || c[i]>=inf) break;


                u[i] = 1;
                c[i] = inf;
                int x = i/K;
                int st = x*K, en = x*K+K;
                b[x] = i;
                for(int l=st; l<en; ++l) if(c[l]<c[b[x]]) b[x] = l;

                for(int k=eb[i]; k; k=es[k]){
                    int j = e[k];
                    int val = d[i] + ec[k];
                    if(val<d[j]){
                        d[j] = val;
                        c[j] = val;

                        int x = j/K;
                        if(c[b[x]]>c[j]) b[x] = j;
                    }
                }

                //for(int j=0;j<D;++j) printf("%d ", c[b[j]]); printf("\n");
                //for(int j=0;j<n;++j) printf("%d ", c[j]); printf("\n");
                //break;
            }

            for(int i=0;i<n;++i) if(d[i]<inf && i!=A) ans = max(ans, d[i]);

        }



        printf("%d\n",ans);

    }


    return 0;
}


