#include <fstream>

using namespace std;
ifstream fin("bibel.in");
ofstream fout("bibel.out");
int op, n, i, dp[25][(1<<18)-1], ans=1e9, poz, j, b[21], cn=1;
struct coord
{
    int x, y;
} a[21], last[21];
int dist(coord a, coord b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
int main()
{
    fin>>op;
    while(op!=2)
    {
        while(op==0)
        {
            fin>>a[n].x>>a[n].y;
            fin>>op;
            n++;
        }
        if(op==1)
        {
            for(i=0; i<cn; i++)
                b[i]=dp[i][(1<<cn)-1];
            for(i=0; i<n; i++)
                for(int mask=0; mask<(1<<n); mask++)
                    dp[i][mask]=1e9;
            for(i=0; i<n; i++)
                for(j=0; j<cn; j++)
                dp[i][(1<<i)]=min(dp[i][(1<<i)], b[j]+dist(a[i], last[j]));
           // dp[0][1]=0;
            ans=1e9;
            for(int mask=0; mask<(1<<n); mask++)
                for(i=0; i<n; i++)
                    if(mask&(1<<i))
                      for(j=0; j<n; j++)
                      if(mask&(1<<j))
                      dp[i][mask]=min(dp[i][mask], dp[j][mask-(1<<i)]+dist(a[j], a[i]));
            for(i=0; i<n; i++)
                ans=min(ans, dp[i][(1<<n)-1]);
            fout<<ans<<'\n';
            fin>>op;
            for(i=0; i<n; i++)
                last[i]=a[i];
            cn=n;
            n=0;
        }

    }
    return 0;
}