1. 


/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: Problem J - Wormholes
* Link: http://uva.onlinejudge.org/contests/240-0682ae4a/p9.html
*
* @author Dennis Wilfert
* @version 1.0, 01/17/2010
*
* Status : Accepted
* Runtime: 5,33s user 0,05s system
*/
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Wormholes {

public static void main(String[] args) throws IOException {

BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));
StringTokenizer token;

int cases = Integer.parseInt(reader.readLine());

final int MAX = 1000000 * 102;

int wormholes, h, i, j, better, transit, cycle, remove;
Coordinate[] wormholeFrom = new Coordinate[50 + 2];
Coordinate[] wormholeTo = new Coordinate[50 + 2];
int[][] wormdata = new int[50 * 2 + 2][2];
int[][] shortest = new int[50 + 2][3];
boolean change;
boolean[] used;

while (cases > 0) {

token = new StringTokenizer(reader.readLine());

// Startkoordinaten
wormholeFrom[0] = wormholeTo[0] = new Coordinate(Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()));
// Zielkoordinaten
wormholeFrom[1] = wormholeTo[1] = new Coordinate(Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()));

wormdata[0][0] = 0;
wormdata[1][0] = 0;


// Anzahl der Wurmlöcher
wormholes = Integer.parseInt(reader.readLine()) + 2;


// Werte einlesen
for (i = 2; i < wormholes; i++) {
token = new StringTokenizer(reader.readLine());
wormholeFrom[i] = new Coordinate(Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()));
wormholeTo[i] = new Coordinate(Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()), Integer.parseInt(token.nextToken()));

wormdata[i][0] = Integer.parseInt(token.nextToken());
wormdata[i][1] = Integer.parseInt(token.nextToken());

}


shortest[0][0] = 0;
// Vorbelegen der Entfernungen mit dem Maximum
for (i = 1; i < wormholes; i++) {
shortest[i][0] = MAX;
}

change = true;

// Solange eine Veränderung gefunden wird erneut durchlaufen um auch negative Zyklen zu finden
while (change) {

change = false;
cycle = -1;

// Bellman-Ford
for (h = 0; h < wormholes; h++) {
for (i = 0; i < wormholes; i++) {
for (j = 0; j < wormholes; j++) {
// Vom Ende des einen Wurmlochs zum Beginn des nächsten
better = shortest[i][0] + wormholeTo[i].distance(wormholeFrom[j]);
// Erstellungszeitpunkt des Wurmlochs muss vor dem aktuellen Zeitpunkt liegen, ansonsten muss bis zum Erstellungszeitpunkt gewartet werden
better = better > wormdata[j][0] ? better : wormdata[j][0];
// Durchquerungszeit dazurechnen
better += wormdata[j][1];
transit = 0;

// Schauen ob der Weg von einem Wurmlochende zum nächsten ohne das Wurmloch zu durchqueren kürzer ist
if (better > shortest[i][0] + wormholeTo[i].distance(wormholeTo[j])) {
better = shortest[i][0] + wormholeTo[i].distance(wormholeTo[j]);
transit = 1;
}
// Von einem Wurmlochende zum nächsten ohne das Wurmloch zu durchlaufen
if (better < shortest[j][0]) {
shortest[j][0] = better;
// Das vorherige Wurmloch merken um Kreise zurückverfolgen zu können
shortest[j][1] = i;
shortest[j][2] = transit;

change = true;
// Kreis wurde gefunden
if (h == wormholes - 1) {
cycle = j;

}
}
}
}
}

// Negative Zyklen zurückverfolgen
if (cycle != -1) {
used = new boolean[wormholes];
remove = MAX;
// Mit dem Endpunkt beginnen den Zyklus zurückverfolgen und in der Queue in der richtigen Reihenfolge speichern
while (!used[cycle]) {
// Wert suchen der vom Ergebnis abgezogen werden kann, falls das Wurmloch durchquert wurde
if (shortest[cycle][2] != 1) {
remove = remove < shortest[cycle][0] - wormdata[cycle][1] - wormdata[cycle][0] ? remove : shortest[cycle][0] - wormdata[cycle][1] - wormdata[cycle][0];
}
used[cycle] = true;
cycle = shortest[cycle][1];

}

// Wert von allen Knoten in diesem Zyklus abziehen
for (i = 0; i < wormholes; i++) {
if (used[i]) {
shortest[i][0] -= remove;
}
}
}
}

writer.println(shortest[1][0]);

cases--;
}
writer.flush();
}
}

/*
* Repräsentiert einen Punkt im Raum
*/
class Coordinate {

private final int x, y, z;

public Coordinate(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}

/*
* Entfernung zu einem anderen Punkt
*/
public int distance(Coordinate o) {
return (int) (Math.ceil(Math.sqrt(((x - o.x) * (x - o.x)) + ((y - o.y) * (y - o.y)) + ((z - o.z) * (z - o.z)))));
}
}