#include <iostream>
#include <vector>
using namespace std;


struct Edge {
 int to, cost;
};

int MaxToLines(vector<vector<Edge>>& edges, int n) {
 int max_cost = -1;
 for (int i = 0; i < n; i++) {

  int biggest_cost1 = -1;
  int biggest_cost2 = -1;
  for (auto& e: edges[i]) {
   if (e.cost > biggest_cost1) {
    biggest_cost1 = e.cost;
   }
   else {
    biggest_cost2 = max(biggest_cost2, e.cost);
   }
  }

  if (biggest_cost1 != -1 && biggest_cost2 != -1) {
   max_cost = max(max_cost, biggest_cost1+biggest_cost2);
  }
 }

 return max_cost;
}

int res = 0;
void dfs(vector<vector<Edge>>& edges, int current, int from, int dist, vector<int>& distance, int& start) {
 if (dist > 2)return;

 for (auto& e: edges[current]) {
  if (distance[e.to] < distance[current] + e.cost && e.to != from) {

   if (e.to == start && dist == 2) {
    distance[e.to] = distance[current] + e.cost;
    res = max(res, distance[e.to]);
   }
   else if (e.to == start && dist != 2) {

   }
   else {
    distance[e.to] = distance[current] + e.cost;
   }


   dfs(edges, e.to, current, dist+1, distance, start);
  }
 }


}


// int MaxInTriangle(vector<vector<Edge>>& edges, int n) {
//  int max_cost = -1;
//  vector<int> dist(n, 0);
//
//  for (int i = n-1; i >=0; i--) {
//   vector<int> dist(n,0);
//   res = 0;
//   dfs(edges, i, -1, 0, dist, i);
//   max_cost = max(max_cost, dist[i]);
//   if (max_cost == 18) {
//    cout<<i<<endl;
//   }
//  }
//
//  return max_cost;
// }

int MaxInTriangle(vector<vector<Edge>>& edges, int n) {
 int max_cost = -1;

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



  for (auto& e: edges[i]) {
   vector<int> dist(n, 0);
   dist[e.to] = max( dist[e.to], dist[i]+e.cost);
   for (auto& e1: edges[i]) {
    if (e1.to != e.to) {
     dist[e1.to] = max( dist[e1.to], dist[i]+e1.cost);
     for (auto& e2: edges[e1.to]) {
      if (e2.to == e.to) {
       max_cost = max(max_cost, dist[e1.to]+dist[e2.to]+e2.cost);
      }
     }
    }
   }
  }

 }

 return max_cost;
}


int S(vector<vector<Edge>>& edges, int n) {
 int Max = 0;
 for (int i = 0; i < n; i++) {
  int sum = 0;
  for (auto& e: edges[i]) {
   sum+=e.cost;
  }
  Max = max(Max, sum);
 }
 return Max;
}

int main(){
 int T;
 cin>>T;

 for (int i = 0; i < T; i++) {
  int n;
  cin>>n;
  vector<vector<Edge>> edges(2*n);
  int result = -1;

  for (int j = 0; j < n; j++) {
   int a,b,c;
   cin>>a>>b>>c;
   a--;
   b--;
   result = max(result, c);
   edges[a].push_back({b, c});
   edges[b].push_back({a, c});
  }

  // if (i == 1) {
  //  for (int j = 0; j < n; j++) {
  //   for (auto e: edges[j]) {
  //    cout<<j<<"->"<<e.to<<" "<<e.cost<<endl;
  //   }
  //  }
  // }

 result = max(result, MaxToLines(edges, 2*n));
  result = max(result, S(edges, 2*n));
  int j = MaxInTriangle(edges, 2*n);
  // cout<<"j - "<<j<<endl;
  result = max(result, j);


cout<<result<<endl;



 }



 return 0;
}

































