Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop

# node class
class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        
# graph class
class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    # 辺の長さを調べる
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    # 辺を追加する
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph

# ダイクストラ法
def dijkstra(graph:list, node:int, start:int, goal:int) -> int:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        if cur_node == goal:
            return dist[goal]
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist[goal]

# input
xs, ys, xt, yt = li()
n = ni()

# グラフにスタートとゴールを追加
g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))

# グラフにそれぞれのバリアを追加
for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))

# バリアを結ぶエッジを追加していく
for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()

# 隣接リストをダイクストラに放り込む
dist = dijkstra(graph, n+2, 0,1)

print(dist)

Fixed submission:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop

# node class
class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        
# graph class
class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    # 辺の長さを調べる
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    # 辺を追加する
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph

# ダイクストラ法
def dijkstra(graph:list, node:int, start:int, goal:int) -> int:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    visited = [False]*node
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        if visited[cur_node]:
            continue
        
        visited[cur_node] = True
        
        if cur_node == goal:
            return dist[goal]
        
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist[goal]

# input
xs, ys, xt, yt = li()
n = ni()

# グラフにスタートとゴールを追加
g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))

# グラフにそれぞれのバリアを追加
for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))

# バリアを結ぶエッジを追加していく
for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()

# 隣接リストをダイクストラに放り込む
dist = dijkstra(graph, n+2, 0,1)

print(dist)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop

# node class
class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        
# graph class
class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    # 辺の長さを調べる
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    # 辺を追加する
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph

# ダイクストラ法
def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

# input
xs, ys, xt, yt = li()
n = ni()

# グラフにスタートとゴールを追加
g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))

# グラフにそれぞれのバリアを追加
for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))

# バリアを結ぶエッジを追加していく
for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()

# 隣接リストをダイクストラに放り込む
dist = dijkstra(graph, n+2, 0)

print(dist[1])


Fixed submission:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop

# node class
class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        
# graph class
class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    # 辺の長さを調べる
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    # 辺を追加する
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph

# ダイクストラ法
def dijkstra(graph:list, node:int, start:int, goal:int) -> int:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    visited = [False]*node
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        if visited[cur_node]:
            continue
        
        visited[cur_node] = True
        
        if cur_node == goal:
            return dist[goal]
        
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist[goal]

# input
xs, ys, xt, yt = li()
n = ni()

# グラフにスタートとゴールを追加
g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))

# グラフにそれぞれのバリアを追加
for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))

# バリアを結ぶエッジを追加していく
for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()

# 隣接リストをダイクストラに放り込む
dist = dijkstra(graph, n+2, 0,1)

print(dist)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop

# node class
class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        
# graph class
class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    # 辺の長さを調べる
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    # 辺を追加する
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph

# ダイクストラ法
def dijkstra(graph:list, node:int, start:int) -> list:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist

# input
xs, ys, xt, yt = li()
n = ni()

# グラフにスタートとゴールを追加
g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))

# グラフにそれぞれのバリアを追加
for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))

# バリアを結ぶエッジを追加していく
for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()

# 隣接リストをダイクストラに放り込む
dist = dijkstra(graph, n+2, 0)

print(dist[1])


Fixed submission:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from math import sqrt
from heapq import heappush, heappop

# node class
class Node(object):
    def __init__(self, num, x, y, r):
        self.num = num
        self.x = x
        self.y = y
        self.r = r
        
# graph class
class Graph(object):
    def __init__(self, num):
        self.graph = [[] for _ in range(num)]
        self.nodes = []
        
    # 辺の長さを調べる
    def calc_edge_len(self, node1, node2):
        dist = sqrt((node1.x - node2.x)**2 + (node1.y - node2.y)**2) - node1.r - node2.r
        if dist <= 0:
            return 0
        else:
            return dist
        
    # 辺を追加する
    def add_edge(self, node1, node2):
        edge_len = self.calc_edge_len(node1, node2)
        self.graph[node1.num].append((edge_len, node2.num))
        self.graph[node2.num].append((edge_len, node1.num))
    
    def get_graph(self):
        return self.graph

# ダイクストラ法
def dijkstra(graph:list, node:int, start:int, goal:int) -> int:
    # 未探索のノードは距離INF
    INF = float("inf")
    dist = [INF]*node
    
    # 始点ノードの距離を0とし、dfsのためのpriority queを作成
    dist[start] = 0
    heap = [(0,start)]
    visited = [False]*node
    
    # 未探索のノードをpriority queueに入れる
    while heap:
        cost, cur_node = heappop(heap)
        
        if visited[cur_node]:
            continue
        
        visited[cur_node] = True
        
        if cur_node == goal:
            return dist[goal]
        
        
        for nex_cost, nex_node in graph[cur_node]:
            dist_cand = dist[cur_node] + nex_cost
            if dist_cand < dist[nex_node]:
                dist[nex_node] = dist_cand
                heappush(heap, (dist[nex_node], nex_node))
    
    return dist[goal]

# input
xs, ys, xt, yt = li()
n = ni()

# グラフにスタートとゴールを追加
g = Graph(n+2)
g.nodes.append(Node(0,xs,ys,0))
g.nodes.append(Node(1,xt,yt,0))

# グラフにそれぞれのバリアを追加
for i in range(n):
    x,y,r = li()
    g.nodes.append(Node(i+2,x,y,r))

# バリアを結ぶエッジを追加していく
for i in range(len(g.nodes)):
    for j in range(i+1, len(g.nodes)):
        g.add_edge(g.nodes[i], g.nodes[j])
        
graph = g.get_graph()

# 隣接リストをダイクストラに放り込む
dist = dijkstra(graph, n+2, 0,1)

print(dist)