Q908: Re-connecting Computer Sites

考慮選擇一個由高速網路線連接 N 個電腦基地所組成的集合 T ，這 N 個電腦基地原本有 M 條連接一對電腦基地的網路線 ，而每條網路線有所需的成本，而你的目標就是找出連接這 N 個電腦基地最小的成本，而所有成本當然就是 T 中所有網路線的成本的總合 ，這個問題其實早已被一些專業人士解決了，但最近添購了 K 條新的網路線。

你的目標就是解出有可能因為新添購的 K 條網路線而產生較低最佳成本的集合 T'，其中有 M+K 條網路線可以使用。

Input

輸入包含多組測資，每組測資內容解釋如下，連續的兩組測資會以一空白行隔開。

每組測資是長成這樣子的:

• 第一行有一個數字 N 代表有幾個電腦基地 (1 <= N <= 1000000)，電腦基地的編號從1...N。
• 再來有 N-1 行代表先前已找到的連結 N 個電腦基地且花費最少成本的集合T， 每行代表一條高速網路線，格式為 a b c，代表 a 和 b 之間的成本是 c ，所有的成本都是整數。
• 再來1行有一個整數 K (1 <= K <= 10)，代表新添購的網路線數目。
• 再來的 K 行每行表示一條新的網路線，表達方式和第2點一樣，所有的花費均為整數。
• 緊接著有一行包含數字 M 代表原本有 M ( N-1 <= M <= N (N-1) / 2) 條網路線。
• 接下來的 M 行，每行代表原本可用的網路線，格式和第2點敘述的一樣，所有的花費亦為整數。

Output

對每組測資輸出兩行，第一行為集合 T 用 M 條網路線所花費在用來連接這 N 個電腦基地的成本。 第二行為集合 T' 用 M+K 條網路線來連接這 N 個電腦基地的最小成本。

如果新的成本和原來的成本一樣，那麼顯然你必須將相同的數字印出兩遍。

Sample Input

5
1 2 5
1 3 5
1 4 5
1 5 5
1
2 3 2
6
1 2 5
1 3 5
1 4 5
1 5 5
3 4 8
4 5 8

Sample Output

20
17