Little I is the manager of a massive railway company. He manages $n$ railway stations, numbered with integers from $1$ to $n$. The railway company has $c$ divisions, and the office of the $i$-th division is located at station $p_i$. Some stations may not have any division offices, while a single station may house multiple division offices.

The $n$ stations are connected by $m$ one-way railways. The $i$-th railway connects station $u_i$ to $v_i$ and is managed by division $r_i$. For management convenience, the office of division $r_i$ is located at either $u_i$ or $v_i$.

Station $1$ (the port) and station $n$ (the capital) are the busiest stations under the company's jurisdiction. To ensure the safety of imported goods, as required by the Ministry of Transport, Little I needs to set up checkpoints on some railways such that every possible route from station $1$ to station $n$ contains at least one railway with a checkpoint.

Little I can notify some divisions (or none at all), requiring these divisions to set up checkpoints on all railways they manage. Little I wants to know the minimum number of divisions that need to be notified to satisfy the requirement. As the newly appointed algorithm engineer, you are ready to show him your skills.

Input

The first line contains three integers $n, m, c$ ($2 \le n, m, c \le 5 \times 10^{4}$), representing the number of railway stations, the number of railways, and the number of divisions, respectively.

The next line contains $c$ integers $p_1, p_2, \dots, p_c$ ($1 \le p_i \le n$), describing the station number where each division's office is located.

The next $m$ lines each contain three integers $u_i, v_i, r_i$ ($1 \le u_i, v_i \le n, 1 \le r_i \le c$), describing a railway. It is guaranteed that $p_{r_i} = u_i$ or $p_{r_i} = v_i$.

Output

Output a single integer representing the minimum number of divisions that need to be notified.

Examples

Input 1

5 10 3
3 1 4
1 3 1
4 3 1
3 2 1
3 5 1
1 2 2
2 1 2
1 4 2
5 1 2
1 4 3
4 5 3

Output 1

2

Note

The railway organization for this example is shown in the figure below, where red, green, and black represent railways managed by divisions 1, 2, and 3, respectively. The optimal strategy is to notify divisions 1 and 3.