Codeforces Round #368 (Div. 2) B. Bakery （水題）

B. Bakery

time limit per test

memory limit per test

input

output

Masha wants to open her own bakery and bake muffins in one of the n cities numbered from 1 to n. There are m

To bake muffins in her bakery, Masha needs to establish flour supply from some storage. There are only k storages, located in different cities numbered a1, a2, ..., ak.

Unforunately the law of the country Masha lives in prohibits opening bakery in any of the cities which has storage located in it. She can open it only in one of another n - k cities, and, of course, flour delivery should be paid — for every kilometer of path between storage and bakery Masha should pay 1

Formally, Masha will pay x roubles, if she will open the bakery in some city b (ai ≠ b for every 1 ≤ i ≤ k) and choose a storage in some city s (s = aj for some 1 ≤ j ≤ k) and b and s are connected by some path of roads of summary length x

Masha is very thrifty and rational. She is interested in a city, where she can open her bakery (and choose one of k

Input

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 105, 0 ≤ k ≤ n) — the number of cities in country Masha lives in, the number of roads between them and the number of flour storages respectively.

Then m lines follow. Each of them contains three integers u, v and l (1 ≤ u, v ≤ n, 1 ≤ l ≤ 109, u ≠ v) meaning that there is a road between cities u and v of length of l

If k > 0, then the last line of the input contains k distinct integers a1, a2, ..., ak (1 ≤ ai ≤ n) — the number of cities having flour storage located in. If k = 0 then this line is not presented in the input.

Output

Print the minimum possible amount of rubles Masha should pay for flour delivery in the only line.

If the bakery can not be opened (while satisfying conditions) in any of the n cities, print  - 1

Examples

input

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

output

3      

input

3 1 1
1 2 3
3      

output

-1      

Note

Image illustrates the first sample case. Cities with storage located in and the road representing the answer are darkened.

題意：給你個無向圖，有k個特殊的點，其他都是普通點，讓你找出一條最短的邊，連接配接特殊的點和普通的點。

題解：把所有的邊都拿出來比較一下就可以了。

代碼：

#pragma comment(linker, "/STACK:102400000,102400000")
//#include<bits/stdc++.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
#include<map>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include <utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mst(a) memset(a, 0, sizeof(a))
#define M_P(x,y) make_pair(x,y)  
#define rep(i,j,k) for (int i = j; i <= k; i++)  
#define per(i,j,k) for (int i = j; i >= k; i--)  
#define lson x << 1, l, mid  
#define rson x << 1 | 1, mid + 1, r  
const int lowbit(int x) { return x&-x; }  
const double eps = 1e-8;  
const int INF = 1e9+7; 
const ll inf =(1LL<<62) ;
const int MOD = 1e9 + 7;  
const ll mod = (1LL<<32);
const int N = 101010; 
const int M=100010; 
template <class T1, class T2>inline void getmax(T1 &a, T2 b) {if (b>a)a = b;}  
template <class T1, class T2>inline void getmin(T1 &a, T2 b) {if (b<a)a = b;}
int read()
{
    int v = 0, f = 1;
    char c =getchar();
    while( c < 48 || 57 < c ){
        if(c=='-') f = -1;
        c = getchar();
    }
    while(48 <= c && c <= 57) 
        v = v*10+c-48, c = getchar();
    return v*f;
}
    
int n,m,k,f[N],x[N],y[N],l[N],t,ans=INT_MAX;
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++)scanf("%d%d%d",x+i,y+i,l+i);
    for(int i=1;i<=k;i++)scanf("%d",&t),f[t]=1;
    for(int i=1;i<=m;i++)
    {
        if(f[x[i]]^f[y[i]])
        ans=min(ans,l[i]);
    }
    if(ans==INT_MAX)
    puts("-1");
    else printf("%d\n",ans); 
    return 0;
}