A country has n cities and m two-way roads.
There are k types of ingredients, and the ith city sells only 1 type Ai. A chef wants to open a restaurant in a city. Every morning, he need to gather all k types of ingredients to his restaurant. The cost of transporting the ingredient from city u to city v is the shortest distance between them.
Find the city that has the lowest transportation cost for him to open the restaurant. It is guaranteed that the answer exists.
Input:
6 9 3
1 2 3 2 1 2
1 2 3
2 4 1
4 6 3
4 1 4
2 5 3
5 1 2
2 6 3
1 3 5
2 3 3
Output:
2