Minimum Notification Problem

A huge railway company is managed by an executive named I. The company has n train stations numbered from 1 to n. There are c divisions, and the office of the i-th division is located at station p_i. Note that a station may have no division office or even more than one.

The n stations are connected by m one‐way railroads. The i-th railroad goes from station u_i to station v_i and is managed by division r_i. It is guaranteed that the office of division r_i is located either at station u_i or at station v_i.

Stations 1 (the port) and n (the capital) are the busiest. To ensure the safety of imported goods, regulations demand that every possible route from station 1 to station n must contain at least one railroad with a checkpoint.

The executive I may notify some divisions (or none) so that all railroads managed by a notified division will have a checkpoint. Your task is to help I to select a set of divisions with the minimum possible size such that every path from station 1 to station n contains at least one railroad belonging to one of the notified divisions.

Input/Output: See the input and output descriptions for details.

Note: If no division is notified, then all railroads are free of checkpoints. Hence, if there exists a path from station 1 to station n using only railroads managed by non‐notified divisions, the condition is not met.

This requirement is equivalent to choosing a subset X of divisions such that in the graph induced by the railroads with r ∉ X there is no path from station 1 to n. The goal is to minimize |X|.

All formulas are to be rendered in LaTeX format.

Mathematically, if we denote a subset X \(\subseteq \{1,2,\dots, c\}\) as the set of divisions notified, the condition is:

$$\text{For every path } P \text{ from } 1 \text{ to } n,\; P \cap \{\text{edges with } r \in X\} \neq \emptyset.$$

Your task is to output the minimum number of divisions that need to be notified.

inputFormat

The first line contains three integers n m c: the number of train stations, railroads, and divisions respectively.

The second line contains c integers: p1 p2 ... pc, where pi denotes the station where the i-th division's office is located.

The following m lines each contain three integers: u v r, meaning there is a one-way railroad from station u to station v managed by division r. It is guaranteed for each such railroad that the office of division r is located at either station u or station v.

outputFormat

Output a single integer, the minimum number of divisions that must be notified so that every path from station 1 to station n contains at least one railroad with a checkpoint.

sample

3 3 2
1 3
1 2 1
2 3 1
1 3 2

2