现代城市生活中最重要的发明之一就是公共交通。然而，大多数人可能并不这么认为——尽管它让城市出行变得容易得多，但我们通常希望在地铁上花费的时间越少越好。

在经历了 NWERC 2009 之后，纽伦堡在你的心中留下了特殊的地位，几年后你决定搬到这里。你唯一的问题是弄清楚该搬到纽伦堡的哪个地方。自然地，你想搬到一个好的街区，但由于该市的大部分地区都很不错，所以仍然有很多选择。由于天生不愿每天花几个小时在通勤上，你决定根据你必须在地铁上花费的时间来选择居住地。

现在，如果你只去一个地方，很容易找到最佳的居住地。但当然，你预计会经常去几个地方，比如工作单位、朋友家以及偶尔去圣婴市场（Christkindlesmarkt）。为了能够计算出这一点，你写下了一份你想经常访问的所有地点的清单，以及你预计去那里的频率。为了简单起见，你假设你总是从家里出发去某个地方，然后返回家中。例如，如果你下班后要去圣婴市场，你会在下班后先回一趟家，然后再去市场，而不是直接从工作单位去市场。现在，你需要找到一个居住地，使得总旅行时间最小。

由于纽伦堡拥有广泛的公共交通系统，你将使用地铁出行。地铁网络相当大，但由于其形状像一棵树，因此仍然相当容易导航。换句话说，任何一对地铁站之间总是存在唯一的一条路径。（对于今天的纽伦堡地铁来说，这并不完全正确，但当你几年后搬到这里时，我们预计它会成为现实。）

输入格式

输入包含多个测试用例。

第一行输入包含一个整数 $c$ ($1 \le c \le 200$)，表示测试用例的数量。

然后，每个测试用例以一个整数 $n$ ($1 \le n \le 50\,000$) 开始，表示纽伦堡的地铁站数量。

接下来有 $n - 1$ 行，描述地铁网络。这些行中的每一行都包含三个整数 $a$、$b$ 和 $t$ ($1 \le a, b \le n$ 且 $1 \le t \le 300$)，表示车站 $a$ 和 $b$ 相邻，且在它们之间旅行需要 $t$ 秒。

接下来是一行，包含一个整数 $m$ ($0 \le m \le n$)，表示你想要经常去的车站数量。

接下来有 $m$ 行。这些行中的每一行都包含两个整数 $a$ 和 $f$ ($1 \le a \le n$ 且 $1 \le f \le 500$)，其中 $a$ 是你想访问的车站，而 $f$ 是你一年中想访问该车站的次数。在此列表中，任何车站最多出现一次。

输出格式

对于每个测试用例，首先输出一行，包含在选择最佳居住地的情况下，一年中在交通上花费的总秒数。

紧接着这一行，输出一行，给出所有最佳的地铁站选择，以单个空格分隔，并按升序排列。

样例

输入样例 1

2
2
1 2 17
2
1 5
2 10
5
1 3 10
2 3 20
3 4 30
4 5 30
3
1 10
2 10
5 20

输出样例 1

170
2
3000
3 4 5