旅行

//考虑暴力的情况下,枚举任意三对点A,B,C，求出A->B->C的距离，取最大作为答案
//对每个中间点求解最短路，排序后取最长的两条边即为该中间点的最大贡献，对贡献取max作为答案
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, m, s;
vector<pii> to[100001];
// int dis[100001];
int dis[1001][1001];
void dij(int U) {
    dis[U][U] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, U});
    while (!pq.empty()) {
        auto [pre, u] = pq.top();
        pq.pop();
        if (pre > dis[U][u])
            continue;
        for (auto [cst, v] : to[u]) {
            if (pre + cst < dis[U][v]) {
                dis[U][v] = pre + cst;
                pq.push({pre + cst, v});
            }
        }
    }
}

void solve(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n;i++)
        to[i].clear();
    memset(dis, 0x7f, sizeof(dis));
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        to[u].push_back({w, v});
        to[v].push_back({w, u});
    }
    int ans = -1;
    for (int i = 1; i <= n;i++){
        dij(i);
        sort(dis[i] + 1, dis[i] + 1 + n);
        int l = n;
        //0会被排序到开头，应该排除
        //l如果小于等于2则有效边数量少于2，对答案无贡献
        while(l>=3&&dis[i][l]==dis[0][0])
            l--;
        if(l<=2)
            continue;
        ans = max(ans, dis[i][l] + dis[i][l - 1]);
    }
    printf("%d\n", ans);
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--)
        solve();
}