|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|3 초||256 MB||85||26||21||30.882%|
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 of the input starts with three integers N M and K, where N is the number of junctions and M is the number of streets in your city, and K is the number of junctions you pass every day (1 ≤ K ≤ N ≤ 10 000, 0 ≤ M ≤ 1 000 000).
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 (1 ≤ ai, bi ≤ N, 1 ≤ ci ≤ 10 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.
Print one line of output containing “yes” if there is another way you can take without losing time, “no” otherwise.
3 3 3 1 2 3 1 2 1 2 3 2 1 3 3
4 5 2 1 4 1 2 2 2 4 1 1 3 1 3 4 2 1 4 2