/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph{
public final boolean IS_DIRECTED;
public final int NUMBER_OF_NODES;
int[][] adjacencyMatrix;
public Graph(boolean isDirected,int n){
IS_DIRECTED = isDirected;
NUMBER_OF_NODES = n;
this.adjacencyMatrix = new int[NUMBER_OF_NODES][NUMBER_OF_NODES];
for(int i=0;i<NUMBER_OF_NODES;i++)
for(int j=0;j<NUMBER_OF_NODES;j++)
this.
adjacencyMatrix[i
][j
] = Integer.
MIN_VALUE; }
public void addEdge(int source,int dest){
addEdge(source, dest, 1);
}
public void addEdge(int source,int dest,int weight){
//if the edge already exists, return without doing anything
if((IS_DIRECTED
&& this.
adjacencyMatrix[source
][dest
]!=Integer.
MIN_VALUE) || (!IS_DIRECTED
&& (this.
adjacencyMatrix[source
][dest
]!=Integer.
MIN_VALUE || this.
adjacencyMatrix[dest
][source
]!=Integer.
MIN_VALUE))) return;
this.adjacencyMatrix[source][dest] = weight;
if(!IS_DIRECTED)
this.adjacencyMatrix[dest][source] = weight;
}
public void removeEdge(int source,int dest){
this.
adjacencyMatrix[source
][dest
] = Integer.
MIN_VALUE; if(!IS_DIRECTED)
this.
adjacencyMatrix[dest
][source
] = Integer.
MIN_VALUE; }
public int maxEdgeWeightOnPath(int source,int dest){
boolean visited[] = new boolean[NUMBER_OF_NODES];
return maxEdgeWeightOnPathUtil(source, dest, visited);
}
public int maxEdgeWeightOnPathUtil(int source,int dest,boolean visited[]){
visited[source] = true;
if(source == dest)
for(int i=0;i<NUMBER_OF_NODES;i++){
if (i
!=source
&& this.
adjacencyMatrix[source
][i
]!=Integer.
MIN_VALUE && !visited
[i
]){ int x = maxEdgeWeightOnPathUtil(i, dest, visited);
return Math.
max(this.
adjacencyMatrix[source
][i
], x
); }
}
}
public long findSum(){
long sum = 0;
for(int i=0;i<NUMBER_OF_NODES;i++)
for(int j=i+1;j<NUMBER_OF_NODES;j++)
sum = sum + maxEdgeWeightOnPath(i, j);
return sum;
}
}
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main
(String[] args
) { try {
int T
= Integer.
parseInt(br.
readLine()); for(int i=0;i<T;i++){
int N
= Integer.
parseInt(br.
readLine()); Graph g = new Graph(false,N);
for(int p=0;p<N-1;p++){
while(st.hasMoreTokens()){
g.
addEdge(Integer.
parseInt(st.
nextToken())-1,
Integer.
parseInt(st.
nextToken())-1,
Integer.
parseInt(st.
nextToken())); }
}
System.
out.
println(g.
findSum()); }
}
e.printStackTrace();
}
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBHcmFwaHsKCQoJcHVibGljIGZpbmFsIGJvb2xlYW4gSVNfRElSRUNURUQ7CgkKCXB1YmxpYyBmaW5hbCBpbnQgTlVNQkVSX09GX05PREVTOwoJCglpbnRbXVtdIGFkamFjZW5jeU1hdHJpeDsKCQoJcHVibGljIEdyYXBoKGJvb2xlYW4gaXNEaXJlY3RlZCxpbnQgbil7CgkJSVNfRElSRUNURUQgPSBpc0RpcmVjdGVkOwoJCU5VTUJFUl9PRl9OT0RFUyA9IG47CgkJdGhpcy5hZGphY2VuY3lNYXRyaXggPSBuZXcgaW50W05VTUJFUl9PRl9OT0RFU11bTlVNQkVSX09GX05PREVTXTsKCQlmb3IoaW50IGk9MDtpPE5VTUJFUl9PRl9OT0RFUztpKyspCgkJCWZvcihpbnQgaj0wO2o8TlVNQkVSX09GX05PREVTO2orKykKCQkJCXRoaXMuYWRqYWNlbmN5TWF0cml4W2ldW2pdID0gSW50ZWdlci5NSU5fVkFMVUU7Cgl9CgkKCXB1YmxpYyB2b2lkIGFkZEVkZ2UoaW50IHNvdXJjZSxpbnQgZGVzdCl7CgkJYWRkRWRnZShzb3VyY2UsIGRlc3QsIDEpOwoJfQoJCglwdWJsaWMgdm9pZCBhZGRFZGdlKGludCBzb3VyY2UsaW50IGRlc3QsaW50IHdlaWdodCl7CgkJLy9pZiB0aGUgZWRnZSBhbHJlYWR5IGV4aXN0cywgcmV0dXJuIHdpdGhvdXQgZG9pbmcgYW55dGhpbmcKCQlpZigoSVNfRElSRUNURUQgJiYgdGhpcy5hZGphY2VuY3lNYXRyaXhbc291cmNlXVtkZXN0XSE9SW50ZWdlci5NSU5fVkFMVUUpIHx8IAoJCQkJKCFJU19ESVJFQ1RFRCAmJiAodGhpcy5hZGphY2VuY3lNYXRyaXhbc291cmNlXVtkZXN0XSE9SW50ZWdlci5NSU5fVkFMVUUgfHwgdGhpcy5hZGphY2VuY3lNYXRyaXhbZGVzdF1bc291cmNlXSE9SW50ZWdlci5NSU5fVkFMVUUpKSkKCQkJcmV0dXJuOwoJCXRoaXMuYWRqYWNlbmN5TWF0cml4W3NvdXJjZV1bZGVzdF0gPSB3ZWlnaHQ7CgkJaWYoIUlTX0RJUkVDVEVEKQoJCQl0aGlzLmFkamFjZW5jeU1hdHJpeFtkZXN0XVtzb3VyY2VdID0gd2VpZ2h0OwoJfQoJCglwdWJsaWMgdm9pZCByZW1vdmVFZGdlKGludCBzb3VyY2UsaW50IGRlc3QpewoJCXRoaXMuYWRqYWNlbmN5TWF0cml4W3NvdXJjZV1bZGVzdF0gPSBJbnRlZ2VyLk1JTl9WQUxVRTsKCQlpZighSVNfRElSRUNURUQpCgkJCXRoaXMuYWRqYWNlbmN5TWF0cml4W2Rlc3RdW3NvdXJjZV0gPSBJbnRlZ2VyLk1JTl9WQUxVRTsKCX0KCglwdWJsaWMgaW50IG1heEVkZ2VXZWlnaHRPblBhdGgoaW50IHNvdXJjZSxpbnQgZGVzdCl7CgkJYm9vbGVhbiB2aXNpdGVkW10gPSBuZXcgYm9vbGVhbltOVU1CRVJfT0ZfTk9ERVNdOwoJCXJldHVybiBtYXhFZGdlV2VpZ2h0T25QYXRoVXRpbChzb3VyY2UsIGRlc3QsIHZpc2l0ZWQpOwoJfQoJCglwdWJsaWMgaW50IG1heEVkZ2VXZWlnaHRPblBhdGhVdGlsKGludCBzb3VyY2UsaW50IGRlc3QsYm9vbGVhbiB2aXNpdGVkW10pewoJCXZpc2l0ZWRbc291cmNlXSA9IHRydWU7CgkJaWYoc291cmNlID09IGRlc3QpCgkJCXJldHVybiBJbnRlZ2VyLk1JTl9WQUxVRTsKCQlmb3IoaW50IGk9MDtpPE5VTUJFUl9PRl9OT0RFUztpKyspewogICAgICAgICAgICBpZiAoaSE9c291cmNlICYmIHRoaXMuYWRqYWNlbmN5TWF0cml4W3NvdXJjZV1baV0hPUludGVnZXIuTUlOX1ZBTFVFICYmICF2aXNpdGVkW2ldKXsKICAgICAgICAgICAgCWludCB4ID0gbWF4RWRnZVdlaWdodE9uUGF0aFV0aWwoaSwgZGVzdCwgdmlzaXRlZCk7CiAgICAgICAgICAgIAlpZih4IT1JbnRlZ2VyLk1JTl9WQUxVRSsxKQogICAgICAgICAgICAJCXJldHVybiBNYXRoLm1heCh0aGlzLmFkamFjZW5jeU1hdHJpeFtzb3VyY2VdW2ldLCB4KTsKICAgICAgICAgICAgfQoJCX0KCQlyZXR1cm4gSW50ZWdlci5NSU5fVkFMVUUrMTsKCX0KCQoJcHVibGljIGxvbmcgZmluZFN1bSgpewoJCWxvbmcgc3VtID0gMDsKCQlmb3IoaW50IGk9MDtpPE5VTUJFUl9PRl9OT0RFUztpKyspCgkJCWZvcihpbnQgaj1pKzE7ajxOVU1CRVJfT0ZfTk9ERVM7aisrKQkJCQoJCQkJc3VtID0gc3VtICsgbWF4RWRnZVdlaWdodE9uUGF0aChpLCBqKTsKCQlyZXR1cm4gc3VtOwoJfQp9CgoKLyogTmFtZSBvZiB0aGUgY2xhc3MgaGFzIHRvIGJlICJNYWluIiBvbmx5IGlmIHRoZSBjbGFzcyBpcyBwdWJsaWMuICovCmNsYXNzIElkZW9uZQp7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmdbXSBhcmdzKSB7CgkJdHJ5IHsKCQkJQnVmZmVyZWRSZWFkZXIgYnIgPSBuZXcgQnVmZmVyZWRSZWFkZXIobmV3IElucHV0U3RyZWFtUmVhZGVyKFN5c3RlbS5pbikpOwoJCQlpbnQgVCA9IEludGVnZXIucGFyc2VJbnQoYnIucmVhZExpbmUoKSk7CgkgICAgICAgIGZvcihpbnQgaT0wO2k8VDtpKyspewoJCSAgICAgICAgaW50IE4gPSBJbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkpOwoJCSAgICAgICAgR3JhcGggZyA9IG5ldyBHcmFwaChmYWxzZSxOKTsKCQkgICAgICAgIGZvcihpbnQgcD0wO3A8Ti0xO3ArKyl7CgkJCSAgICAgICAgU3RyaW5nVG9rZW5pemVyIHN0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihici5yZWFkTGluZSgpLCIgIik7CgkJCSAgICAgICAgd2hpbGUoc3QuaGFzTW9yZVRva2VucygpKXsKCQkJICAgICAgICAJZy5hZGRFZGdlKEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpLTEsIEludGVnZXIucGFyc2VJbnQoc3QubmV4dFRva2VuKCkpLTEsSW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSkpOwoJCQkgICAgICAgIH0KCQkgICAgICAgIH0KCQkgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihnLmZpbmRTdW0oKSk7CgkgICAgICAgIH0KCQl9IAoJCWNhdGNoIChJT0V4Y2VwdGlvbiBlKSB7CgkJCWUucHJpbnRTdGFja1RyYWNlKCk7CgkJfQoJfQoJCn0=