2015 German Collegiate Programming Contest (GCPC)

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?


The first line starts with three integers n, m and k (1kn104, 0m106), 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, 1ci104). 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.


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
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
Source 2015 German Collegiate Programming Contest (GCPC), June 20, Problem E