Bessie, luôn luôn muốn cuộc sống của mình tốt hơn, đã thấy rõ rằng cô ta thật sự rất thích ghé thăm ~n~ ~(1 \le n \le P)~ cánh đồng yêu thích ~F_i~ trong tổng số ~P~ ~(1 \le P \le 500~; ~1 \le F_i \le P)~ cánh đồng (được đánh số từ 1 ~\rightarrow P)~ thuộc sơ hữu của nông dân John.

Bessie biết rằng cô ấy có thể xác định được ~C~ ~(1 \le C \le 8000)~ con đường hai chiều (được đánh số ~1~ ...~C)~ kết nối tất cả các cánh đồng trong toàn bộ nông trại. Ứng với mỗi con đường ~P_i~ là thời gian đi ~T_i~ ~(1 \le T_i \le 892)~ và nối ~2~ cánh đồng ~a_i~ và ~b_i~ ~(1 \le a_i \le P~; ~1 \le b_i \le P)~.

Bessie muốn tìm cánh đồng tốt nhất để ngủ thỏa mãn bình quân thời gian để đi đến ~n~ cánh đồng yêu thích của cô ta là nhỏ nhất.

Ví dụ, hãy xem xét một nông trang được trình bày như một bản đồ dưới đây, nơi đánh dấu * là cách đồng được yêu thích. Các số trong ngoặc là thời gian tương ứng để di chuyển giữa ~2~ cánh đồng.

            1*--[4]--2--[2]--3
                     |       |
                    [3]     [4]
                     |       |
                     4--[3]--5--[1]---6---[6]---7--[7]--8*
                     |       |        |         |
                    [3]     [2]      [1]       [3]
                     |       |        |         |
                    13*      9--[3]--10*--[1]--11*--[3]--12*

Bảng sau đây cho thấy các khoảng cách trung bình nếu nghỉ tại các cánh đồng ~4, 5, 6, 7, 9, 10, 11~, và ~12~: $$\begin{array}{|l|l|l|l|l|l|l|l|} \hline & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Cánh đồng } & \mbox{Trung bình} \\ & 1 & 8 & 10 & 11 &12 & 13 & \mbox {khoảng cách} \\ \hline 4 & 7 & 16 & 5 & 6 & 9 & 3 & \frac{46}{6} = 7.67 \\ \hline 5 & 10 & 13 & 2 & 3 & 6 & 6 & \frac{40}{6} = 6.67 \\ \hline 6 & 11 & 12 & 1 & 2 & 5 & 7 & \frac{38}{6} = 6.33 \\ \hline 7 & 16 & 7 & 4 & 3 & 6 & 12 & \frac{48}{6} = 8.00 \\ \hline 9 & 12 & 14 & 3 & 4 & 7 & 8 & \frac{48}{6} = 8.00 \\ \hline 10 & 12 & 11 & 0 & 1 & 4 & 8 & \frac{36}{6} = 6.00 \\ \hline 11 & 13 & 10 & 1 & 0 & 3 & 9 & \frac{36}{6} = 6.00 \\ \hline 12 & 16 & 13 & 4 & 3 & 0 & 12 & \frac{48}{6} = 8.00 \\ \hline \end{array}$$

Kết quả tối ưu là cánh đồng ~10~

Input

• Dòng ~1~: ~3~ số nguyên ~P~, ~n~, ~C~
• Dòng ~2~ ...~n + 1~: Dòng ~i + 2~ chứa ~1~ số nguyên ~F_i~
• Dòng ~n + 2~ ...~C + n + 1~: Mỗi dòng chứa ~3~ số Nguyên ~a_i, b_i, F_i~ mô tả ~1~ con đường ~2~ chiều là thời gian di chuyển giữa chúng.

Output

• Gồm ~1~ dòng duy nhất là cánh đồng được chọn. nếu có nhiều kết quả, chọn cánh đồng có chỉ số nhỏ nhất!

Sample Input

13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7

Sample Output

10