Masha wants to open her own bakery and bake muffins in one of the n cities numbered from 1 to n. There are m bidirectional roads, each of whose connects some pair of cities.

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 a_1, a_2, ..., a_{k}.

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 ruble.

Formally, Masha will pay x roubles, if she will open the bakery in some city b (a_{i} ≠ b for every 1 ≤ i ≤ k) and choose a storage in some city s (s = a_{j} for some 1 ≤ j ≤ k) and b and s are connected by some path of roads of summary length x (if there are more than one path, Masha is able to choose which of them should be used).

Masha is very thrifty and rational. She is interested in a city, where she can open her bakery (and choose one of k storages and one of the paths between city with bakery and city with storage) and pay minimum possible amount of rubles for flour delivery. Please help Masha find this amount.


-----Input-----

The first line of the input contains three integers n, m and k (1 ≤ n, m ≤ 10^5, 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 ≤ 10^9, u ≠ v) meaning that there is a road between cities u and v of length of l kilometers .

If k > 0, then the last line of the input contains k distinct integers a_1, a_2, ..., a_{k} (1 ≤ a_{i} ≤ 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 in the only line.


-----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]

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

Difficulty: interview

Starter code:

Solutions:
n,m,k = (int(i) for i in input().split())
r = []
for i in range(m):
    u,v,p = (int(i) for i in input().split())
    r += [(p,u,v)]
if k == 0:
    print(-1)
    return
else:
    s = list(map(int,input().split()))
    sklad = [False]*n
    for i in range(len(s)):
        sklad[s[i]-1] = True
        
    ans = 10**10
    for i in range(len(r)):
        if sklad[r[i][1]-1] != sklad[r[i][2]-1]:
            ans = min(ans,r[i][0])
            
if ans == 10**10:
    print(-1)
else:
    print(ans)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

N,M,K = list(map(int,input().split()))

ftcs = []
for m in range(M):
    f,t,c=list(map(int,input().split()))
    ftcs.append((f,t,c))
if K != 0:
    storages = list(map(int,input().split()))
else:
    storages = []
storages_s = set(storages)

mn = 1e20
for f,t,c in ftcs:
    if (f in storages_s and t not in storages_s) or \
       (t in storages_s and f not in storages_s):
        mn = min(mn, c)
if mn == 1e20:
    print(-1)
else:
    print(mn)

    
        

    


n, m, k = list(map(int, input().split()))
g = {}

for _ in range(m):
    u, v, l = list(map(int, input().split()))
    if not (u - 1) in g:
        g[u - 1] = []
    if not (v - 1) in g:
        g[v - 1] = []

    g[u - 1].append((v - 1, l))
    g[v - 1].append((u - 1, l))

storages = [] if k == 0 else list([int(x) - 1 for x in input().split()])
isstor = [False for _ in range(n)]
for s in storages:
    isstor[s] = True

best = float('inf')
for s in storages:
    if not s in g:
        continue
    for ne in g[s]:
        if isstor[ne[0]]:
            continue
        else:
            best = min(best, ne[1])

print(-1 if best == float('inf') else best)


from sys import stdin, stdout
n, m, k = map(int, stdin.readline().split())
vertices = [[] for i in range(n + 1)]
for i in range(m):
    a, b, w = map(int, stdin.readline().split())
    vertices[a].append((b, w))
    vertices[b].append((a, w))


if k:
    storages = set(map(int, stdin.readline().split()))
    ans = float('inf')
    for num in storages:
        for v in vertices[num]:
            if v[0] not in storages:
                ans = min(ans, v[1])
    if ans == float('inf'):
        stdout.write('-1')
    else:
        stdout.write(str(ans))
else:
    stdout.write('-1')

line1=input().split()
n=int(line1[0]) #Num cities
m=int(line1[1]) #Num roads
k=int(line1[2]) #Num storagecities

roads=[]
for i in range (m):
    line=input().split()
    line[0],line[1],line[2]=int(line[0]),int(line[1]),int(line[2])
    roads.append(line)


cities={}
for i in range (n):
    cities[i+1]=False

if (k>0):
    line=input().split()
    for c in line:
        cities[int(c)]=True

best=-1

for road in roads:
    u=road[0]
    v=road[1]
    l=road[2]
    if cities[u] == (not cities[v]):
        if best==-1:
            best=l
        else:
            best=min(best,l)
print (best)


n, m, k = map(int, input().split())
A = [0] * m
for i in range(m):
    A[i] = list(map(int, input().split()))
if k != 0:
    ans = set(list(map(int, input().split())))
if k == 0 or k == n:
    print(-1)
else:
    per = float('infinity')
    for i in range(m):
        if (A[i][0] in ans and A[i][1] not in ans) or (A[i][0] not in ans and A[i][1] in ans):
            per = min(per, A[i][2])
    if per != float('infinity'):
        print(per)
    else:
        print(-1)

def solve():
    n, m, k = list(map(int, input().split()))
    r = {}
    for _ in range(m):
        u, v, l = list(map(int, input().split()))
        if u not in r:
            r[u] = []
        if v not in r:
            r[v] = []
        r[u].append((v, l))
        r[v].append((u, l))
    a = set()
    s = [False] * (n + 1)
    if k > 0:
        a = set(map(int, input().split()))
    for a_ in a:
        s[a_] = True
    ans = float('inf')
    for a_ in a:
        if a_ not in r:
            continue
        for t in r[a_]:
            if s[t[0]]:
                continue
            ans = min(ans, t[1])

    print(-1 if ans == float('inf') else ans)


def main():
    solve()


def __starting_point():
    main()

__starting_point()

import sys
from decimal import *

def main():

    n,m,k = list(map(int, sys.stdin.readline().split()))

    e = [[] for i in range(n)]
    sk = [False for i in range(n)]

    for i in range(m):
        u,v,l = list(map(int, sys.stdin.readline().split()))
        u = u-1
        v = v-1
        e[u].append((v,l))
        e[v].append((u,l))

    if k>0:
        x = list(map(int, sys.stdin.readline().split()))
        for i in x:
            sk[i-1]=True

    best = None
    for i in range(n):
        if sk[i]:
            continue
        for j in range(len(e[i])):
            a, l = e[i][j]
            if sk[a]:
                if best is None:
                    best = l
                elif best>l:
                    best = l
    if best is None:
        print(-1)
    else:
        print(best)    


main()


import sys
import collections


n, m, k = list(map(int, str.split(sys.stdin.readline())))
if k == 0:

    print(-1)

else:

    d = collections.defaultdict(set)
    for _ in range(m):

        u, v, l = list(map(int, str.split(sys.stdin.readline())))
        d[u].add((v, l))
        d[v].add((u, l))

    aks = set(map(int, str.split(sys.stdin.readline())))
    cheapest = None
    for source in aks:

        for destination, l in d[source]:

            if destination not in aks:

                if cheapest is None:

                    cheapest = l

                else:

                    cheapest = min(cheapest, l)

    print(cheapest or -1)


#!/usr/bin/env python3.5
import sys
import heapq


def add_edge(edges, a, b, c):
    edges.append((a, b, c))


def read_graph():
    n, m, k = list(map(int, next(sys.stdin).split()))
    edges = []
    for _ in range(m):
        a, b, c = list(map(int, next(sys.stdin).split()))
        add_edge(edges, a, b, c)
        add_edge(edges, b, a, c)
    stores = set(list(map(int, next(sys.stdin).split())) if k > 0 else [])
    return edges, stores


def solve(edges, stores):
    best = None
    for a, b, c in edges:
        if (
            a in stores and b not in stores
            or b in stores and a not in stores
        ): 
            if best is None or c < best:
                best = c
    return best


def __starting_point():
    edges, stores = read_graph()
    ans = solve(edges, stores)
    print(ans or -1)

__starting_point()

def binary_search(seq, t):
    min = 0
    max = len(seq) - 1
    while True:
        if max < min:
            return -1
        m = (min + max) // 2
        if seq[m] < t:
            min = m + 1
        elif seq[m] > t:
            max = m - 1
        else:
            return m
n, m, k = [int(i) for i in input().split()]
s = [[] for i in range(n)]
for i in range(m):
	u, v, l = [int(i) for i in input().split()]
	s[u-1].append([v-1, l])
	s[v-1].append([u-1, l])
if k == 0 or k == n:
	print(-1)
else:
	o = [int(i)-1 for i in input().split()]
	o.sort()
	a = 10**9+1
	for i in o:
		for j in s[i]:
			if binary_search(o, j[0]) == -1:
				a = min(j[1], a)
	if a == 10**9+1:
		print(-1)
	else:
		print(a)
	


import sys
sys.setrecursionlimit(20000)

from collections import Counter
from math import ceil, floor, factorial, fsum, isinf, exp, log, log10, log2, isfinite
from itertools import product

def getlist(tcast):
	return [tcast(x) for x in input().strip().split(' ')]
def getval(tcast):
	return tcast(input().strip())
def getmatrix(r, tcast):
	mat = []
	for i in range(r):
		mat.append(getlist(tcast))
	return mat

def isodd(n):
    return n & 1
def numdigits(n):
    return len(str(n)) - (1 if n < 0 else 0)
def primesupto(n):
    isp = [True] * (n + 1)
    isp[0], isp[1] = False, False
    for i, x in enumerate(isp): #for each number
        if x: #found a prime
            mults = i * i
            while mults <= n:
                isp[mults] = False
                mults += i
    return isp
def maxarrays(a, b):
    return [max(x, y) for x, y in zip(a, b)]

nv, ne, ns = getlist(int)
if ns == 0 or ne == 0:
    print(-1)
else:
    edges = []
    for i in range(ne):
        start, end, weight = getlist(int)
        edges.append((start, end, weight))

    starts = getlist(int)
    checkstart = set(starts)
    best = 100000000000000000
    cur = 0
    for edge in edges:
        a, b = edge[0], edge[1]
        if a in checkstart and b not in checkstart or b in checkstart and a not in checkstart:
            best = min(best, edge[2])

    print(-1 if best == 100000000000000000 else best)


n,m,k = list(map(int,input().split()))
graph = {}
vertices = set()
ans = -1
floor = [False] * (n+1)
for i in range(m):
	u,v,l = list(map(int,input().split()))
	if u not in vertices : 
		vertices.update([u])
		graph[u] = []
	if v not in vertices : 
		vertices.update([v])
		graph[v] = []
	graph[u].append([v,l])
	graph[v].append([u,l])
if k!= 0 :
	A = []
	for i in input().split():
		floor[int(i)] = True
		A.append(int(i))
	valids = []
	for x in A:
		if x in vertices:
			for nb in graph[x]:
				if not floor[nb[0]]:
					valids.append(nb[1])
	if len(valids)>0 :
		ans = min(valids)

print(ans)




#!/usr/bin/env python3

try:
    while True:
        n, m, k = list(map(int, input().split()))
        edges = [tuple(map(int, input().split())) for i in range(m)]
        if k == 0:
            print(-1)
        else:
            bachery = [False] * n
            for x in map(int, input().split()):
                bachery[x - 1] = True
            result = 1e10
            for u, v, length in edges:
                u -= 1
                v -= 1
                if bachery[u]:
                    if not bachery[v]:
                        result = min(result, length)
                elif bachery[v] and not bachery[u]:
                    result = min(result, length)

            if result > 5e9:
                print(-1)
            else:
                print(result)

except EOFError:
    pass


def main():
	n, m, k = map(int, input().split())
	graph = [[] for i in range(n + 1)]
	for i in range(m):
		u, v, l = map(int, input().split())
		graph[u].append((v, l))
		graph[v].append((u, l))


	if k == 0:
		print(-1)
		return
		

	a = list(map(int, input().split()))
	check = [True for i in range(n + 1)]
	for x in a:
		check[x] = False
	ans = 10 ** 10
	for x in a:
		if graph[x] != []:
			for y in graph[x]:
				if check[y[0]]:
					ans = min(ans, y[1])

	if ans == 10 ** 10:
		ans = -1
	print(ans)
		







		




def __starting_point():
	main()
__starting_point()

n,m,k = list(map(int,input().split()))
if k==0 or k==n:
    print(-1)
else:
    has = [[] for i in range(n)]
    edge = []
    for i in range(m):
        a,b,c = list(map(int,input().split()))
        edge.append([a-1,b-1,c])
    bad = [False]*n
    bads = list(map(int,input().split()))
    for i in bads:
        bad[i-1] = True
    ans = 10**18
    for e in edge:
        if bad[e[0]]!=bad[e[1]]:
            ans = min(ans,e[2])
    print(ans if ans<10**18 else -1)


n, m, k = [int(i) for i in input().split()]


roads = []
storages = [False]*n

for i in range(m):
    roads.append([int(x) for x in input().split()])

sto = []
if k > 0:
    sto = [int(i) for i in input().split()]
for i in sto:
    storages[i-1] = True


minimum = None
for a,b,c in roads:
    if (storages[a-1] and not storages[b-1]) or (not storages[a-1] and storages[b-1]):
        if minimum is None or c < minimum:
            minimum = c

if minimum is None:
    print(-1)
else:
    print(minimum)


n, m, k = map(int, input().split())

g = [[] for i in range(n)]
for i in range(m):
    s, v, w = map(int, input().split())
    s, v = s - 1, v - 1
    g[s].append((v, w))
    g[v].append((s, w))

if not k:
    print(-1)
    return

stores = {num - 1 for num in map(int, input().split())}
minw = float('inf')
for s in stores:
    for v, w in g[s]:
        if v not in stores:
            minw = min(minw, w)
print(minw if minw != float('inf') else -1)

def update_min(v):
    nonlocal min_
    for u, w in list(graph[v].items()):
        if not is_whouse[u]:
            min_ = min(min_, w)

min_ = 10000000000000000
n, m, k = list(map(int, input().split()))
graph = [dict() for i in range(n)]
for i in range(m):
    u, v, l = list(map(int, input().split()))
    u -= 1
    v -= 1
    if v in list(graph[u].keys()):
        graph[u][v] = min(l, graph[u][v])
    else:
        graph[u][v] = l
    if u in list(graph[v].keys()):
        graph[v][u] = min(l, graph[v][u])
    else:
        graph[v][u] = l
if k:
    whouses = list(map(int, input().split()))

    is_whouse = [False for i in range(n)]
    for w in whouses:
        is_whouse[w - 1] = True
    for w in whouses:
        update_min(w - 1)
    if min_ == 10000000000000000:
        print(-1)
    else:
        print(min_)
else:
    print(-1)


import sys
f = sys.stdin

n, m, k = list(map(int, f.readline().strip().split()))

d = dict()
for i in range(m):
    u, v, l = list(map(int, f.readline().strip().split()))
    if d.get(u, -1) == -1:
        d[u] = [[v, l]]
    else:
        d[u].append([v, l])    
        
    if d.get(v, -1) == -1:
        d[v] = [[u, l]]        
    else:
        d[v].append([u, l])
    

if k == 0:
    print(-1)
else:
     
    a = {int(t): 1 for t in f.readline().strip().split()}
        
    s = 2* 10**9    
    city = -1
    
    for it in a:
        if d.get(it, -1) == -1:
            continue
        l_city = d[it]
        for c in l_city:
            if s > c[1] and a.get(c[0], -1) == -1:
                s = c[1]
                city = c[0]
    
    if city == -1:
        print(-1)     
    else:
        print(s)  



import sys

n, m, k = list(map(int, input().split()))

links = [[int(i) for i in input().split()] for i in range(m)]

if k == 0:
    print(-1)
    return

flour_cities = set(int(i) for i in input().split())

shortest_path = float('inf')
shortest_path_exists = False

for u, v, l in links:
    u_has_flour = u in flour_cities
    v_has_flour = v in flour_cities
    if (u_has_flour and not v_has_flour) or (not u_has_flour and v_has_flour):
        shortest_path_exists = True
        shortest_path = min(l, shortest_path)

if shortest_path_exists:
    print(shortest_path)
else:
    print(-1)


n,m,k = list(map(int,input().split()))
uvl = [list(map(int,input().split())) for i in range(m)]
if k == 0:
    print("-1")
else:
    ai = list(map(int,input().split()))
    ai.sort()
    ans = 1000000001
    def bf(x):
        l = 0
        r = k - 1
        while l < r:
            mid = (l + r)//2;
            if (ai[mid] < x):
                l = mid + 1
            else:
                r = mid
        if ai[r] == x:
            return 1
        else:
            return 0
    for i in range(m):
        if bf(uvl[i][0]) != bf(uvl[i][1]):
            ans = min(ans,uvl[i][2])
    if ans == 1000000001:
        print("-1")
    else:
        print(ans)


inp = input().strip().split()

n,m,k = int(inp[0]),int(inp[1]),int(inp[2])

c1= [-1 for i in range(m+1)]
c2= [-1 for i in range(m+1)]
l= [-1 for i in range(m+1)]
store= [False for i in range(n+1)]

for i in range(m):
    inp = input().strip().split()
    c1[i],c2[i],l[i] = int(inp[0]),int(inp[1]),int(inp[2])

if(k<=0):
    print("-1")
else:
    inp = input().strip().split()
    ans=1000000000+10
    for i in inp:
        store[ int(i) ] = True
    for i in range(m):
        x,y,d= c1[i],c2[i],l[i]
        if( store[x] and (not store[y]) ):
            ans=min(ans,d)
        if( store[y] and (not store[x]) ):
            ans=min(ans,d)
    if(ans == 1000000000+10):
        print("-1")
    else:
        print(ans)


mat = []
pek = set()

n, m, k = list(map(int, input().split()))
arr = []
for i in range(m):
    u, v, l = list(map(int, input().split()))
    arr.append([l, u, v])
if k:
    pek = set(map(int, input().split()))
    arr.sort()
    for i in range(m):
        if arr[i][1] in pek and arr[i][2] not in pek:
            print(arr[i][0])
            return
        if arr[i][2] in pek and arr[i][1] not in pek:
            print(arr[i][0])
            return
    print(-1)
else:
    print(-1)


n,m,k = [int(x) for x in input().split()]
distance = {}
edge = {}
for i in range (1,n+1):
	edge[i] = []
	distance[i] = -1
for i in range (1,m+1):
	u,v,l = [int(x) for x in input().split()]
	edge[u].append((v,{'nei' : v, 'dis' : l}))
	edge[v].append((u,{'nei' : u, 'dis' : l}))
if(k!=0):
    a = [int(x) for x in input().split()]
    for z in a:
    	distance[z] = 0
    for uu in a:
    	frontier = [uu]
    	while frontier:
    		next = []
    		for u in frontier:
    			for (v,vv) in edge[u]:
    				jarak = vv.get('dis')
    				if (distance[v] == -1):
    					distance[v] = jarak + distance[u]
    					next.append(v)
    				else:
    					if(jarak + distance[u] < distance[v]):
    						next.append(v)
    						distance[v] = jarak + distance[u]
    		frontier = next
    minim = 1000000000
    cek = False
    for uu in distance:
    	if(distance[uu]!=-1 and distance[uu]!=0):
    		minim = min(minim,distance[uu])
    		cek = True
    if cek:		
    	print(minim)
    else:
    	print(-1)
else:
    print(-1)