TIOJ 2164

#include <bits/stdc++.h>
#include <time.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define int long long

int x[5001], y[5001], z[5001];
int dist[5001][5001];
int key[5001];
int pre[5001];
bool choose[5001];

int32_t main(){
    int n;
    scanf("%lld", &n);
    if(n > 5000)return 0;
    for(int i = 1; i <= n; ++i){
        scanf("%lld%lld%lld", x+i, y+i, z+i);
        key[i] = 1e18;
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= n; ++j){
            dist[i][j] += (x[i]-x[j])*(x[i]-x[j]);
            dist[i][j] += (y[i]-y[j])*(y[i]-y[j]);
            dist[i][j] += (z[i]-z[j])*(z[i]-z[j]);
        }
    }
    int ans = 0;
    key[1] = 0;
    for(int i = 1; i <= n; ++i){
        int small = -1;
        for(int j = 1; j <= n; ++j){
            if(!choose[j] && (small == -1 || key[j] < key[small])){
                small = j;
            }
        }
        choose[small] = 1;
        ans += dist[small][pre[small]];
        //cout << small << ' ' << pre[small] << '\n';
        for(int j = 1; j <= n; ++j){
            if(key[j] > dist[small][j]){
                key[j] = dist[small][j];
                pre[j] = small;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}