Processing math: 100%
Restaurant - MarisaOJ: Marisa Online Judge

Restaurant

Time limit: 3000 ms
Memory limit: 256 MB

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

  • The first line contains 3 integers n,m,k.
  • The second line contains n integers Ai.
  • The next m lines, each line contains 3 integers u,v,w, there is a road of length wi between u and v.

Output

  • Print the optimal city. If there are more than 1 optimal city, print the city with the smallest index.

Constraints

  • 1≤n≤105.
  • 1≤k≤50.
  • 1≤Ai≤k.
  • 1≤u,v≤n.
  • 1≤w≤109.

Example

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