{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n现代城市生活中最重要的发明之一是公共交通系统。然而,大多数人可能不会这样考虑,尽管它使城市内的出行变得更加容易,但我们通常希望在地铁上度过尽可能少的时间。\n\n在你参加了2009年NWERC比赛后,纽伦堡在你的心中留下了特殊的位置,几年后你决定搬到这里。唯一的问题是确定搬到纽伦堡的哪个地区。当然,你想搬到一个好的社区,但由于城市的大部分地方都很不错,所以仍然有很多选择。你不愿意每天花费数小时通勤,所以决定选择一个地方,基于你将在地铁上花费的时间。\n\n现在,如果你只打算去一个地方,找到最佳的居住地就很容易。但当然,还有一些地方,你预计会定期去,比如工作、朋友和偶尔的Christkindlesmarkt。为了能够解决这个问题,你已经列出了所有你想经常访问的地方的清单,以及你想去那里的频率的估计。为了简化问题,你假设你总是去某个地方然后回家,例如,如果你下班后要去Christkindlesmarkt,你会在去市场之前从工作地点经过家,而不是直接从工作地点去市场。现在,你需要找到一个居住地,使得总的旅行时间最短。\n\n由于纽伦堡有一个庞大的公共交通系统,你将使用地铁出行。地铁网络非常庞大,但因为它的形状像一棵树,所以仍然很容易操作。换句话说,任何两个地铁站之间都有唯一的路径。(这对于今天的纽伦堡地铁来说并不完全正确,但当你几年后搬到这里时,我们预计它将成为事实。)\n\n"}},{"title":"输入","value":{"format":"HTML","content":"输入由多个测试用例组成。输入的第一行包含一个整数c(1 \u003c\u003d c \u003c\u003d 200),表示测试用例的数量。然后,每个测试用例以一个整数n(1 \u003c\u003d n \u003c\u003d 50,000)开始,表示纽伦堡的地铁站数量。然后是n行,描述地铁网络。每行包含三个整数a、b和t(1 \u003c\u003d a, b \u003c\u003d n,1 \u003c\u003d t \u003c\u003d 300),表示车站a和b相邻,并且在它们之间旅行需要t秒。接下来是一行包含一个整数m(0 \u003c\u003d m \u003c\u003d n),表示你想要定期去的车站数量。然后是m行,每行包含两个整数a和f(1 \u003c\u003d a \u003c\u003d n,1 \u003c\u003d f \u003c\u003d 500),其中a是你想要访问的车站,f是你想要在一年内访问这个车站的次数。此清单中的任何车站都不会出现多次。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,首先输出一行包含在一年内花费在交通上的秒数,前提是你选择了一个最佳的居住地。随后输出一行,列出所有最佳选择的地铁站,用单个空格分隔,按递增顺序排列。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2\r\n1 2 17\r\n2\r\n1 5\r\n2 10\r\n5\r\n1 3 10\r\n2 3 20\r\n3 4 30\r\n4 5 30\r\n3\r\n1 10\r\n2 10\r\n5 20\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e170\r\n2\r\n3000\r\n3 4 5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}