/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
private static final int MOD = 1000000007;
private static final int MAX = 6;
private static List<Node> list = new ArrayList<Node>(MAX);
private static int[] id = new int[MAX];
private static long[] size = new long[MAX];
int n, a, b, w;
long result;
int tc
= Integer.
parseInt(br.
readLine()); for (int t = 0; t < tc; t++) {
n
= Integer.
parseInt(br.
readLine());
initialize(n);
for (int i = 0; i < n - 1; i++) {
inputs = br.readLine().split(" ");
list.add(new Node(a, b, w));
}
result = 0;
for (int i = 0; i < n - 1; i++) {
a = root(list.get(i).x);
b = root(list.get(i).y);
result = (result + (list.get(i).w * size[a] * size[b])) % MOD;
union(a, b);
}
list.clear();
}
}
private static void initialize(int n) {
for (int i = 0; i <= n; i++) {
id[i] = i;
size[i] = 1;
}
}
private static int root(int i) {
while (id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
private static void union(int x, int y) {
if (size[x] < size[y]) {
id[x] = y;
size[y] += size[x];
} else {
id[y] = x;
size[x] += size[y];
}
}
}
class Node implements Comparable<Node> {
int x, y, w;
public Node(int x, int y, int w) {
this.x = x;
this.y = y;
this.w = w;
}
@Override
public int compareTo(Node obj) {
if (this.w == obj.w) {
return this.x - obj.x;
}
return this.w - obj.w;
}
@Override
return "Node [x=" + x + ", y=" + y + ", w=" + w + "]";
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBJZGVvbmUgewoJcHJpdmF0ZSBzdGF0aWMgZmluYWwgaW50IE1PRCA9IDEwMDAwMDAwMDc7Cglwcml2YXRlIHN0YXRpYyBmaW5hbCBpbnQgTUFYID0gNjsKIAoJcHJpdmF0ZSBzdGF0aWMgTGlzdDxOb2RlPiBsaXN0ID0gbmV3IEFycmF5TGlzdDxOb2RlPihNQVgpOwoJcHJpdmF0ZSBzdGF0aWMgaW50W10gaWQgPSBuZXcgaW50W01BWF07Cglwcml2YXRlIHN0YXRpYyBsb25nW10gc2l6ZSA9IG5ldyBsb25nW01BWF07CiAKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluKFN0cmluZ1tdIGFyZ3MpIHRocm93cyBFeGNlcHRpb24gewoJCUJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsKIAoJCWludCBuLCBhLCBiLCB3OwoJCWxvbmcgcmVzdWx0OwoJCVN0cmluZ1tdIGlucHV0czsKIAoJCWludCB0YyA9IEludGVnZXIucGFyc2VJbnQoYnIucmVhZExpbmUoKSk7CgkJZm9yIChpbnQgdCA9IDA7IHQgPCB0YzsgdCsrKSB7CgkJCW4gPSBJbnRlZ2VyLnBhcnNlSW50KGJyLnJlYWRMaW5lKCkpOwogCgkJCWluaXRpYWxpemUobik7CiAKCQkJZm9yIChpbnQgaSA9IDA7IGkgPCBuIC0gMTsgaSsrKSB7CgkJCQlpbnB1dHMgPSBici5yZWFkTGluZSgpLnNwbGl0KCIgIik7CgkJCQlhID0gSW50ZWdlci5wYXJzZUludChpbnB1dHNbMF0pOwoJCQkJYiA9IEludGVnZXIucGFyc2VJbnQoaW5wdXRzWzFdKTsKCQkJCXcgPSBJbnRlZ2VyLnBhcnNlSW50KGlucHV0c1syXSk7CiAKCQkJCWxpc3QuYWRkKG5ldyBOb2RlKGEsIGIsIHcpKTsKCQkJfQogCgkJCUNvbGxlY3Rpb25zLnNvcnQobGlzdCk7CgkJCXJlc3VsdCA9IDA7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgbiAtIDE7IGkrKykgewoJCQkJYSA9IHJvb3QobGlzdC5nZXQoaSkueCk7CgkJCQliID0gcm9vdChsaXN0LmdldChpKS55KTsKCQkJCXJlc3VsdCA9IChyZXN1bHQgKyAobGlzdC5nZXQoaSkudyAqIHNpemVbYV0gKiBzaXplW2JdKSkgJSBNT0Q7CgkJCQl1bmlvbihhLCBiKTsKCQkJfQoJCQkKCQkJbGlzdC5jbGVhcigpOwoJCQlTeXN0ZW0ub3V0LnByaW50bG4ocmVzdWx0KTsKCQl9Cgl9CiAKCXByaXZhdGUgc3RhdGljIHZvaWQgaW5pdGlhbGl6ZShpbnQgbikgewoJCWZvciAoaW50IGkgPSAwOyBpIDw9IG47IGkrKykgewoJCQlpZFtpXSA9IGk7CgkJCXNpemVbaV0gPSAxOwoJCX0KCX0KIAoJcHJpdmF0ZSBzdGF0aWMgaW50IHJvb3QoaW50IGkpIHsKCQl3aGlsZSAoaWRbaV0gIT0gaSkgewoJCQlpZFtpXSA9IGlkW2lkW2ldXTsKCQkJaSA9IGlkW2ldOwoJCX0KIAoJCXJldHVybiBpOwoJfQogCglwcml2YXRlIHN0YXRpYyB2b2lkIHVuaW9uKGludCB4LCBpbnQgeSkgewoJCWlmIChzaXplW3hdIDwgc2l6ZVt5XSkgewoJCQlpZFt4XSA9IHk7CgkJCXNpemVbeV0gKz0gc2l6ZVt4XTsKCQl9IGVsc2UgewoJCQlpZFt5XSA9IHg7CgkJCXNpemVbeF0gKz0gc2l6ZVt5XTsKCQl9Cgl9CgkKfQogCmNsYXNzIE5vZGUgaW1wbGVtZW50cyBDb21wYXJhYmxlPE5vZGU+IHsKCWludCB4LCB5LCB3OwogCglwdWJsaWMgTm9kZShpbnQgeCwgaW50IHksIGludCB3KSB7CgkJdGhpcy54ID0geDsKCQl0aGlzLnkgPSB5OwoJCXRoaXMudyA9IHc7Cgl9CiAKCUBPdmVycmlkZQoJcHVibGljIGludCBjb21wYXJlVG8oTm9kZSBvYmopIHsKCQlpZiAodGhpcy53ID09IG9iai53KSB7CgkJCXJldHVybiB0aGlzLnggLSBvYmoueDsKCQl9CiAKCQlyZXR1cm4gdGhpcy53IC0gb2JqLnc7Cgl9CglAT3ZlcnJpZGUKCXB1YmxpYyBTdHJpbmcgdG9TdHJpbmcoKSB7CgkJcmV0dXJuICJOb2RlIFt4PSIgKyB4ICsgIiwgeT0iICsgeSArICIsIHc9IiArIHcgKyAiXSI7Cgl9Cn0K