题目：旅行（牛客）

include<bits/stdc++.h>

using namespace std;
int t;

int const N=1e3+7;
int const M=1e3+7;
struct L{
int dis,a;
friend bool operator<(L a,L b){ //这里的a,b表示在队列里的顺序，即a在b前
return a.dis > b.dis ; //因为堆是优先级小的在前，大的在后，且堆是优先级大的出队，即队尾（top）出队（即小的出列），所以重载时a(前面的)要大于b(后面的)
//堆的补充：堆访问到的元素也是优先级大的即top;默认大者优先
}
};

//链式前向星
int cnt,head[N]; //head表示头位置
// 存图
struct node{
    int u; //点的序号 
    int len;  //长度 
    int next;   //指向的下一个点 
}edge[M << 1];  // M << 1 是因为此图为无向边，无向边等于两条有向边，所以要*2 
//加边
void add(int x,int y,int len){  // x为起点，y为终点，此函数表示从x到y有一条权值为len的有向边
    edge[++cnt].u=y;
    edge[cnt].len=len;
    edge[cnt].next=head[x];
    head[x]=cnt;
}
//dijkstra
int dis[N],vis[N];  //dis表示i到原点的距离  
int dijkstra(int s){
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    //priority_queue<pair<int,int>,vector< pair<int,int> >,greater< pair<int,int> > > pq;
    priority_queue<L> pq;
    dis[s]=0;
    //pq.push( pair<int,int>(0,s) );
    pq.push((L){0,s});
    int x=0,y=0;
    while(!pq.empty()){
        //pair<int,int> now=pq.top();pq.pop();
        L now=pq.top();pq.pop();
        //int u=now.second;
        int u=now.a ;
        if(vis[u]) continue;
        vis[u]=1;
        y=max(y,dis[u]);
        if(y>x) swap(x,y);
        for(int i=head[u];i;i=edge[i].next){
            if( vis[edge[i].u] ) continue;
            //松弛
            if( dis[edge[i].u] > dis[u] +edge[i].len ){
                dis[edge[i].u]=dis[u]+edge[i].len ;
                //pq.push( pair<int,int>(dis[edge[i].u],edge[i].u) );
                pq.push( (L){dis[edge[i].u],edge[i].u} );
            }
        }
    }
    if(y==0) return 0;
    return x+y;
}

int main(){
cin >> t;
while(t--){
cnt=0;
memset(head,0,sizeof(head));
int n,m;
cin >> n >> m;
for(int i=1;i<=m;++i){
int a,b,c;
cin >> a >> b >> c;
add(a,b,c);add(b,a,c);
}
int ans=0;
for(int i=1;i<=n;++i){
ans=max(ans,dijkstra(i));
}
if(ans) cout << ans << endl;
else cout << -1 << endl;
}
return 0;
}