Question: Ramadan is the time when restaurants make a lot of money in Ankara and there are already N restaurants (numbered from 1 to N) with given number of daily visitors. You know how to make the best Ayran in the world. It is so good that all restaurants want to hire you and even if you won’t choose them they are ready to buy Ayran from the restaurant you are working in.

You don’t care about money at all and the only important thing for you is to deliver Ayran to as many people as possible. But the problem is that Ayran loses its original taste if it is delivered to places further than M meters from you.

If there are E direct roads between restaurants select one of them, so that the number of people who could taste your original Ayran is maximum.

Input specification
On the first line there three integers N, M, E (1 ≤ N ≤ 500, M ≤ 10,000, E < 150,000). On the second line there are N integers v_i – number of visitors in restaurant i (vi ≤ 1,000). Each of next E lines contains three integers fi, ti, li, where fi and ti – numbers of restaurants connected, li – the length of the road in meters (1 ≤ fi, ti ≤ 500, 0 < li ≤ 10,000).

Output specification
The number of the restaurant you have chosen. If there are more than one restaurants giving the same result, print the restaurant with the smallest number.