e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

ADA University - February 3 - Dijkstra

Change of Scenery

Every day you drive to work using the same roads as it is the shortest way. This is efficient, but over time you have grown increasingly bored of seeing the same buildings and junctions every day. So you decide to look for different routes. Of course you do not want to sacrifice time, so the new way should be as short as the old one. Is there another way that differs from the old one in at least one street?

Input

The first line starts with three integers n, m and k (1kn10 000, 0m1 000 000), where n is the number of junctions, m is the number of streets in your city and k is the number of junctions you pass every day.

The next line contains k integers, the (1-based) indices of the junctions you pass every day. The first integer in this line will always be 1, the last integer will always be n. There is a shortest path from 1 to n along the k junctions given.

m lines follow. The i-th of those lines contains three integers ai, bi, ci and describes a street from junction ai to junction bi of length ci (1ai, bin, 1ci10 000). Streets are always undirected.

Note that there may be multiple streets connecting the same pair of junctions. The shortest path given uses for every pair of successive junctions a and b a street of minimal length between a and b.

Output

Print one line containing "yes" if there is another way you can take without losing time and "no" otherwise.

Time limit 1 second
Memory limit 128 MiB
Input example #1
3 3 3
1 2 3
1 2 1
2 3 2
1 3 3
Output example #1
yes
Input example #2
4 5 2
1 4
1 2 2
2 4 1
1 3 1
3 4 2
1 4 2
Output example #2
no
Source 2015 German Collegiate Programming Contest (GCPC), June 20, Problem E