In the last decades, rural areas have progressively lost more and more inhabitants that have emigrated to big cities. That lowered the number of children living in villages so much that made it economically impos- sible to have a school in each of the villages and, even less, a specialised teacher in each of them. For that reason, a lot of teachers in rural areas have several villages assigned and during the day they have to go and teach in all of them to enlighten the minds of the kids. The music teacher has been in this situation for years. Each year he is assigned up to 6 different villages he has to visit compulsorily everyday. Fortunately, he can design the timetables for his classes to minimize the number of kilometers he travels. After giving it a lot of thought and tired of spending hours and hours in the road, he decided to start renting. Every year, after visiting all the villages where he has to teach, he will decide where to live and in what order to visit schools. But he has no idea how to make that selection. Information about the roads is easy to obtain in the form of tables of the segments of roads between the different villages and the distance between them. The most difficult part is to find out what village minimizes the number of daily kilometers he has to travel. Specially because under no circumstances he will choose to live in one of the villages where he teaches, since he doesn’t want to meet his students when he goes shopping. Input Input is composed by several test cases, each of them representing the information of the roads of a region and several years of the teacher’s life where the assigned villages change. Each of the test cases starts with a line with two numbers, nv and nr, with the number of villages of the region (2 ≤ nv ≤ 1,000) and the number of roads in the region (nr ≤ 10,000). After that, there will be nr lines with the information about the roads, which are composed by two numbers indicating the villages that are linked (between 1 and nv) and the kilometers that separate them. Keep in mind that there could be roads sharing both origin and destination villages and that there could even be rural roads that start and end in the same village (useful for farmers to go around their lands). Then, there will be a number c, indicating the number of different courses for which you will be asked (at most 100). The following c lines will contain the information about the village assignation from that course (between 1 and 6) and the identifiers from each village. Output For each test case, you will write a line for each course taught in the region. Each of the lines will contain two numbers: the identifier of the village where the teacher has to move to and the number of kilometers travelled by car daily. It is guaranteed that there will always be a solution. If there is more than one village that minimizes the travelled distance, choose the village with the lowest identifier (those villages with lower identifier have also lower rents). After each test case, write a line with three dashes (---).
2/2 Sample Input 21 121 1 11 45 121 131 141 231 241 2 212 3412 Sample Output 22 --- 33 34 ---