#12223Moving to Nuremberg

★★★★

時間限制：2000 毫秒記憶體限制：64 MB

One of the most important inventions for modern-day city life is the public transportation. However, most people probably do not think of it that way — even though it makes travel in the city a lot easier, we generally want to spend as little time as possible on the subway.

After your experience in NWERC 2009, Nuremberg holds a special place in your heart, and some years later you decide to move here. Your only problem is to figure out which part of Nuremberg to move to. Naturally, you want to move to a nice neighborhood, but since most parts of the city are nice there are still a lot of choices. Being naturally averse to spending hours each day on commuting, you instead decide to choose a place based on the amount of time you will have to spend on the subway.

Now, if you were only going to go to one place, it would be easy to find the best place to live. But of course, there are several places where you anticipate that you will go regularly, such as work, friends, and the occasional Christkindlesmarkt. In order to be able to work this out, you have written a list of all the places which you want to visit regularly, along with estimates of how often you want to go there. For simplicity, you assume that you will always go somewhere and then back home, e.g., if you are going to Christkindlesmarkt after work you will drop by your house on the way from work before going to the markt, rather than going to the markt directly from work. Now, you have to find the place to live for which the total travel time is minimal.

範例輸入 1

範例輸出 1

Pro 專屬功能：查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.

Because Nuremberg has an extensive public transportation system, you will be using the subway for traveling. The subway net is quite big, but is still fairly easily maneuvered because it is shaped like a tree. In other words, there is always a unique path between any pair of subway stations. (This is not quite true for the Nuremberg subway of today, but when you move here in a few years, we anticipate that it will be true.)

Input

The input consists of several test cases. The first line of input contains an integer c (1 ≤ c ≤ 200), giving the number of test cases. Then, each test case starts with an integer n (1 ≤ n ≤ 50000), giving the number of subway stations in Nuremberg. Then follow n − 1 lines, describing the subway net. Each of these lines contains three integers a, b, and t (1 ≤ a, b ≤ n, and 1 ≤ t ≤ 300), indicating that stations a and b are adjacent and that it takes t seconds to travel between them. This is followed by a line containing an integer m (0 ≤ m ≤ n), denoting the number of stations which you want to go to regularly. Then follow m lines. Each of these lines contains two integers a and f (1 ≤ a ≤ n, 1 ≤ f ≤ 500), where a is the station you want to visit and f is the number of times you want to visit this station in a year. No station will occur in this list more than once.

Output

For each test case, first output a line containing the number of seconds spent in traffic during a year, provided you choose an optimal place to live. Following this line, output a line giving all optimal choices of subway stations, separated by single spaces and in increasing order.