A country has $n$ cities and $m$ two-way roads.
There are $k$ types of ingredients, and the $i^{th}$ city sells only 1 type $A_i$. 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 $A_i$.
- The next $m$ lines, each line contains 3 integers $u, v, w$, there is a road of length $w_i$ 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 \le n \le 10^5$.
- $1 \le k \le 50$.
- $1 \le A_i \le k$.
- $1 \le u, v \le n$.
- $ 1 \le w \le 10^9$.
### 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
```
