#include <fstream>
#define MAX 17
#define INF 1000000000
using namespace std;
ifstream cin ("bibel.in");
ofstream cout ("bibel.out");
int dp[(1 << MAX) + 10][MAX + 10], dpAnt[MAX + 10];
struct ura
{
    int x, y;
};
ura v[MAX + 10], vAnt[MAX + 10];
int dist(ura a, ura b)
{
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
int main()
{
    int type, nAnt = 1;
    cin >> type;
    while (type != 2)
    {
        int n = 0;
        while (type == 0)
        {
            n++;
            cin >> v[n].x >> v[n].y >> type;
        }
        if (type == 1)
        {
            for (int c = 0; c < (1 << n); c++)
                for (int i = 1; i <= n; i++)
                    dp[c][i] = INF;
            for (int i = 1; i <= nAnt; i++)
                for (int j = 1; j <= n; j++)
                    dp[1 << (j - 1)][j] = min(dp[1 << (j - 1)][j], dpAnt[i] + dist(v[j], vAnt[i]));
            for (int c = 0; c < (1 << n); c++)
                for (int last = 1; last <= n; last++)
                    if (c & (1 << (last - 1)))
                        for (int added = 1; added <= n; added++)
                            if (!(c & (1 << (added - 1))))
                                dp[c | (1 << (added - 1))][added] = min(dp[c | (1 << (added - 1))][added], dp[c][last] + dist(v[last], v[added]));
            /*for (int c = 0; c < (1 << n); c++)
            {
                for (int i = 1; i <= n; i++)
                    cout << dp[c][i] << ' ';
                cout << '\n';
            }*/
            int ans = INF;
            nAnt = n;
            for (int i = 1; i <= n; i++)
            {
                ans = min(ans, dp[(1 << n) - 1][i]);
                vAnt[i] = v[i];
                dpAnt[i] = dp[(1 << n) - 1][i];
            }
            cout << ans << '\n';
            cin >> type;
        }
    }
    return 0;
}