import math import heapq def main(): n = int(input()) planets = [] for _ in range(n): x, y, t = map(int, input().split()) r = math.hypot(x, y) planets.append((x, y, t, r)) # Build adjacency list adj = [[] for _ in range(n)] for i in range(n): xi, yi, ti, ri = planets[i] for j in range(n): if i == j: continue xj, yj, tj, rj = planets[j] if ti != tj: d_sq = (ri - rj) ** 2 else: dx = xi - xj dy = yi - yj d_sq = dx * dx + dy * dy adj[i].append((j, d_sq)) # Dijkstra's algorithm to find minimal maximum edge weight INF = float('inf') max_dist = [INF] * n max_dist[0] = 0 # Starting at node 0 (planet 1) heap = [] heapq.heappush(heap, (0.0, 0)) while heap: current_max, u = heapq.heappop(heap) if u == n - 1: break if current_max > max_dist[u]: continue for v, w in adj[u]: new_max = max(current_max, w) if new_max < max_dist[v]: max_dist[v] = new_max heapq.heappush(heap, (new_max, v)) s = max_dist[n - 1] # Compute the ceiling with epsilon to handle precision issues result = math.ceil(s - 1e-9) print(result) if __name__ == "__main__": main()