#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cstring>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#include <cmath>
#define infi 1147483645
#define x first
#define y second
using namespace std;

ifstream f("bibel.in");
ofstream g("bibel.out");

int dp[(1<<17)+5][17],N1=1,N2,q,x,y,T,ct,best[21],i,j,k;

vector<pair<int,int> > v(25);

int dist(pair<int,int> a,pair<int,int> b)
    {
        return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }

void solve()
    {
        for(i=0;i<1<<N2;++i)
            for(j=0;j<N2;++j)
                dp[i][j]=infi;

        for (i=0;i<N1;++i)
        {
            dp[(1<<N1)-1][i]=best[i];
        }
        /*if (v[0]==make_pair(0,0))
            v.erase(v.begin());*/
        for(i=1;i<1<<N2;++i)
            for(j=1;j<N2;++j)
                if (i & (1<<j))
                    for (k=0;k<N2;++k)
                        if (i & (1<<k) && k!=j)
                            {
                                dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k] + dist(v[k],v[j]));
                            }
        int rasp=infi;
        for (i=0;i<N2;++i)
        {
            if (dp[(1<<N2)-1][i] < rasp && dp[(1<<N2)-1][i])
                rasp=dp[(1<<N2)-1][i];
            best[i]=dp[(1<<N2)-1][i];
        }
        g<<rasp<<'\n';


    }


int main()
{
    v[N2++]=make_pair(0,0);
    while(1)
    {
        f>>q;
        while(q == 0)
        {
            f>>x>>y>>q;
            v[N2++]=make_pair(x,y);
        }
        if (q == 1)
        {
            solve();
            N1=N2;
        }
        if (q == 2)
            break;
    }

    return 0;
}