Frog

#include <iostream>

using namespace std;

const int N = 1000;
int n, a[N][N], shortJump[N], D[N];
bool visited[N];

struct Leaf {
  int x, y, r;  
};

Leaf l[N];

void input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l[i].x >> l[i].y >> l[i].r;
        visited[i] = false;
        shortJump[i] = 0;
        for (int j = 0; j < n; j++) {
            a[i][j] = -1;
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int d1 = l[i].x - l[j].x;
            int d2 = l[i].y - l[j].y;
            int left = d1 * d1 + d2 * d2;
            int right1 = 40 + l[i].r + l[j].r;
            int right2 = 90 + l[i].r + l[j].r;
            
            if (left <= right1 * right1) a[i][j] = a[j][i] = 0;
            else if (left <= right2 * right2) a[i][j] = a[j][i] = 1;
        }
    }
}

void dijkstra(int u) {
    for (int i = 0; i < n; i++) {
        D[i] = 1e9;
    }
    D[u] = 0;
    visited[u] = true;
    
    for (int i = 0; i < n; i++) {
        int uBest = 0;
        int maxDif = 1e9;
        for (int j = 0; j < n ; j++) {
            if (D[j] < maxDif && !visited[j]) {
                uBest = j;
                maxDif = D[j];
            }
        }
        visited[uBest] = true;
        for(int j = 0; j < n; j++) {
            if (a[uBest][j] == -1) continue;
            int diff = D[uBest] + a[uBest][j];
            if (diff < D[j]) {
                D[j] = diff;
                shortJump[j] = shortJump[uBest] + (a[uBest][j] == 0);
            }
            else if (diff == D[j]) {
                shortJump[j] = min(shortJump[j], shortJump[uBest] + (a[uBest][j] == 0));
            }
        }
    }
}

int main(){
    freopen("input.txt", "r", stdin);
    int t;
    cin >> t;
    for (int tc = 1; tc <= t; tc++) {
        input();
        dijkstra(0);
        if (D[n - 1] == 1e9) {
            cout << -1 << endl;
        }
        else {
            cout << D[n - 1] << " " << shortJump[n - 1] << endl;
        }
    }
    return 0;
}