City Mapping

Peanut is going for a holiday to the city Silvermill, and therefore he needs a map of Silvermill. Unfortunately, his computer is broken, and so he cannot Google for the map.

Silvermill is a city consisting of N road junctions, numbered 1 to N, and N − 1 roads, with each road i connecting two road junctions Ai and Bi in both directions. This road also takes Wi minutes to traverse in either direction. It is guranteed that the city is fully connected, meaning it is possible to travel from any road junction to any other road junction using the roads in the city. To avoid congestion, the governor of Silvermill has decided that there will be no more than three roads connected to each junction in the city.

Peanut needs to obtain a map of Silvermill. In other words, he needs to obtain (Ai, Bi, Wi) for i = 1, . . . , N − 1.

Peanut has hired a cartographer in Silvermill to accomplish this task. As the cartographer is not very skilled, he can only answer a very simple question: what is the minimum amount of time, in minutes, required to travel between road junctions X and Y ? Peanut did not pay enough money to this cartographer, so he only answers Q such questions before he quits his job.

Peanut needs you to help him to design a list of questions so that he can map out Silvermill and enjoy his holiday. Can you help him?

문제

제한