from heapq import*
N,M,K=map(int,input().split())
gr=[[] for i in range(N)]
C=list(map(int,input().split()))
for i in range(M):
    u,v=map(int,input().split())
    gr[u-1].append((v-1,C[i]))
    gr[v-1].append((u-1,C[i]))
dist=[[1<<60]*(K+1) for i in range(N)]
dist[0][0]=0
hq=[(0,0,0)]
while hq:
    d,p,c=heappop(hq)
    for np,cs in gr[p]:
        if dist[np][c]>d+cs:
            dist[np][c]=d+cs
            heappush(hq,(d+cs,np,c))
        if c!=K and dist[np][c+1]>d:
            dist[np][c+1]=d
            heappush(hq,(d,np,c+1))
ans=min(dist[-1])
if ans==(1<<60):
    print(-1)
else:
    print(ans)