발전소 설치(백준 1277)

import sys
import heapq 
import math 
calc = lambda x,y : math.sqrt((x[1]-y[1])*(x[1]-y[1])+(x[2]-y[2])*(x[2]-y[2])) 
input =sys.stdin.readline 
inf = int(1e9)
n,w =map(int, input().split())
m = float(input())
points = [[0,0,0]] 
gra= [[]for _ in range(n+1)] 
dist =[inf for _ in range(n+1)]
# dist[1] =0 


for i in range(n):
    x,y= map(int, input().split())
    points.append((i+1, x,y))
for i in range(w):
    a,b = map(int, input().split())
    gra[a].append((b,0))
    gra[b].append((a,0))

for i in range(1,n):
    for j in range(i+1,n+1):
        distance = calc(points[i] , points[j])
        if( distance <= m):
            gra[i].append((j, distance))
            gra[j].append((i, distance))
            
        
    
def dijk(start):
    q =[[0,start]]
    dist[start] = 0 
    heapq.heapify(q)
    while q :
        
        dist1 ,now = heapq.heappop(q)
        if dist1 > dist[now]:
            
            continue 
        for nextnode,cost in (gra[now]):
            if dist1+ cost < dist[nextnode] :
                dist[nextnode] = dist1+ cost 
                heapq.heappush(q, (dist[nextnode], nextnode))

dijk(1)
print(int(1000* dist[n]))