#include #include #define rep2(i, k, n) for (i64 i = (i64)(k); i < (i64)(n); i++) #define rep(i, n) rep2(i, 0, n) #define all(x) begin(x), end(x) #ifdef ENV_LOCAL #define dump \ if (1) cerr #else #define dump \ if (0) cerr #endif using namespace std; using namespace std::string_literals; using i32 = int32_t; using i64 = int64_t; using f64 = double; using f80 = long double; using vi32 = vector; using vi64 = vector; // using namespace harudake; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); i64 n; cin >> n; vector> vp; rep(i, n) { i64 x, y, t; cin >> x >> y >> t; vp.emplace_back(x, y, t); } vector vis(n, false); i64 INF = 1e18; vi64 mins(n, INF); mins[0] = 0; rep(i, n) { i64 idx = -1; i64 mn = INF; rep(j, n) { if (vis[j]) continue; if (mins[j] < mn) { mn = mins[j]; idx = j; } } vis[idx] = true; auto [x, y, t] = vp[idx]; rep(j, n) { auto d = [&] { auto [xj, yj, tj] = vp[j]; if (t != tj) { i64 rsq1 = x * x + y * y; i64 rsq2 = xj * xj + yj * yj; i64 val = ceil(rsq1 + rsq2 - 2 * sqrt(rsq1 * rsq2)); return val; } else { i64 xd = x - xj; i64 yd = y - yj; return xd * xd + yd * yd; } }(); if (mins[j] > max(mins[idx], d)) { mins[j] = max(mins[idx], d); } } } cout << mins.back() << endl; return 0; }