You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

Format

Input

第1行输入三个整数P，F C.之后F行每行输入一个整数表示一个贝茜喜欢的牧场．之后C行每行输入三个整数ai，bi，Ti，描述一条路。

Output

一个整数，满足题目要求的最佳牧场．如果有多个答案，输出编号最小的。

Samples

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

10

Limitation

对于100%的数据：P<=500，C<=8000，Ti<=892