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

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

int dp[(1<<18)+5][19],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()
    {
        memset(dp,inf,sizeof(dp));

        for (i=0;i<N1;++i)
        {
            dp[(1<<N1)-1][i]=best[i];
        }

        for(i=1;i<1<<N2;++i)
            for(j=0;j<N2;++j)
                if (i & (1<<j))
                    for (k=0;k<N2;++k)
                        if (i & (1<<k))
                            {
                                dp[i][j]=min(dp[i][j],dp[i^(1<<j)][k] + dist(v[k],v[j]));
                            }
        int rasp=inf;
        for (i=0;i<N2;++i)
        {
            if (dp[(1<<N2)-1][i]<rasp)
                rasp=dp[(1<<N2)-1][i];
            best[i]=dp[(1<<N2)-1][i];
        }
        g<<rasp<<'\n';


    }


int main()
{
    v[N2++]=make_pair(x,y);
    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;
}