caidistra

#include <iostream>

using namespace std;

int n;
const int oo = 99999999;

double abss(double n)
{
	if (n < 0) return -n;
	else return n;
}
double canbac2(double left, double right, int n)
{
	double mid = (left + right)/2;
	//cout << mid  <<" " << mid*mid << endl;
	if (abss(mid*mid - n) < 0.0000001)
		return mid;

	if (mid*mid < n) return  canbac2(mid,right, n);
	else return canbac2(left, mid, n);
}

struct point{
	int x;
	int y;
	int r;
};

point a[1002];
int map[1003][1002];
int nhayngan[1000];
int dem[1000];
int kt[1000];
int chiphi[1002];

int khoangcach(point aa, point bb)
{
	int h1 = abss(aa.x - bb.x);
	int h2 = abss(aa.y - bb.y);
	int bp = h1*h1 + h2*h2;
	double kc = canbac2(0, bp, bp);
	kc = kc - aa.r - bb.r;

	if (kc <= 40) return 1;
	else if (kc > 40 && kc <= 90) return 500;
	else return 0;
}

void dijkstra()
{
	for (int i = 1; i<=n; i++)
	{
		chiphi[i] = oo;
		kt[i] = 0;
		dem[i] = 0;
		nhayngan[i] = 0;
	}

	chiphi[1] = 0;
	
	while (true)
	{
		int minn = oo;
		int pos = -1;
		for (int i = 1; i<=n; i++)
		if (kt[i] == 0 && chiphi[i] < minn)
		{
			minn = chiphi[i];
			pos = i;
		}

		if (pos == -1) break;
		kt[pos] = 1;

		for (int i = 1; i<= n; i++)
			if (kt[i] == 0 && map[pos][i] != 0 && chiphi[i] > chiphi[pos] + map[pos][i])
			{
				chiphi[i] = chiphi[pos] + map[pos][i];
				if (map[pos][i] == 1)
					nhayngan[i] = nhayngan[pos] + 1;
				else nhayngan[i] = nhayngan[pos];
				dem[i] = dem[pos] + 1;
			}
	}
}
int main()
{
	//freopen("input.txt","r",stdin);


	int ntc;
	cin >> ntc;
	for (int tc=1; tc<=ntc; tc++)
	{
		int tmp;
		cin >> n;
		for (int i = 1; i<=n; i++)
			cin >> a[i].x >> a[i].y >> a[i].r;
		
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (i!=j)
				{
					map[i][j] = khoangcach(a[i], a[j]);
				}

	    /*for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
				cout << map[i][j] << " ";
			cout << endl;
		}*/

		dijkstra();

		if (chiphi[n] == oo)
			cout << -1 << endl;
		else cout << dem[n] - nhayngan[n] << " "<< nhayngan[n] << endl;
	}
	return 0;
}