Кодерун рисует карту Манхэттена и отмечает на ней ...

Кодерун рисует карту Манхэттена и отмечает на ней точки интереса с разной зоной притяжения. Ему нужно понять, как связать эти точки с минимальной суммарной стоимостью так, чтобы локальные зоны оставались достижимыми.

На плоскости расположено n n точек с целочисленными координатами. Точка с номером i i задаётся координатами ( x i , y i ) (xi​,yi​) и целым радиусом интереса r i ri​, причём 0 ≤ x i , y i ≤ 1 09 0≤xi​,yi​≤109 и 0 ≤ r i ≤ 2 ⋅ 1 09 0≤ri​≤2⋅109.

Расстояние между точками — манхэттенское:

d ( i , j ) = ∣ x i − x j ∣ + ∣ y i − y j ∣ .
d(i,j)=∣xi​−xj​∣+∣yi​−yj​∣.

Зоной интереса точки i i называется множество точек, лежащих в пределах её радиуса:

S i = {   j : d ( i , j ) ≤ r i   } .
Si​={j:d(i,j)≤ri​}.

Заметим, что всегда i ∈ S i i∈Si​, поскольку d ( i , i ) = 0 ≤ r i d(i,i)=0≤ri​.

Требуется выбрать множество рёбер E E полного графа на данных точках с минимальной суммарной стоимостью (стоимость ребра ( u , v ) (u,v) равна d ( u , v ) d(u,v)) так, чтобы для каждой точки i i все точки её зоны S i Si​ оказались в одной компоненте связности графа ( V , E ) (V,E). Путь между двумя точками из S i Si​ может проходить через любые точки графа, не обязательно принадлежащие S i Si​.

Решение всегда существует: в худшем случае можно напрямую соединить все требуемые точки.
Формат ввода

text
В первой строке задано число тестов t t.
Каждый блок начинается со строки с числом точек n n.
В следующих n n строках записаны по три целых числа x i xi​, y i yi​, r i ri​  — координаты и радиус i i-й точки.

Ограничения:

text
1 ≤ t ≤ 25   000 1≤t≤25000
1 ≤ n ≤ 1 05 1≤n≤105
0 ≤ x i , y i ≤ 1 09 0≤xi​,yi​≤109
0 ≤ r i ≤ 2 ⋅ 1 09 0≤ri​≤2⋅109
суммарное значение n n по всем тестам не превосходит 120   000 120000
суммарный размер всех зон интереса в одном тесте удовлетворяет ∑ i ∣ S i ∣ ≤ 1 06 ∑i​∣Si​∣≤106

Формат вывода

Для каждого теста выведите выбранный лес рёбер в следующем формате:

text
в первой строке  — минимальную суммарную стоимость S S;
во второй строке  — число выбранных рёбер m m;
в каждой из следующих m m строк  — пару чисел u u и  v v ( 1 ≤ u , v ≤ n 1≤u,v≤n, u ≠ v u=v): концы выбранного ребра. Точки нумеруются с единицы в порядке ввода.

Сумма стоимостей выбранных рёбер должна равняться S S и быть минимально возможной, а сами рёбра должны делать связной зону S i Si​ каждой точки. Оптимальный лес не единствен — засчитывается любой лес минимальной суммарной стоимости.

Лес содержит не более n — 1 n—1 рёбер, стоимость каждого не превосходит 2 ⋅ 1 09 2⋅109, поэтому минимальная стоимость удовлетворяет 0 ≤ S ≤ ( n — 1 ) ⋅ 2 ⋅ 1 09 < ; 2 ⋅ 1 014 < ; 263 0≤S≤(n—1)⋅2⋅109<;2⋅1014<;263 и гарантированно помещается в 64-битное знаковое целое.
Примечание

В первом тесте точка 1 1 имеет радиус r 1 = 1 r1​=1, поэтому S 1 = { 1 , 2 } S1​={1,2} (точка 2 2 на расстоянии d ( 1 , 2 ) = 1 ≤ 1 d(1,2)=1≤1) — их необходимо связать. Аналогично S 2 = { 1 , 2 } S2​={1,2}. Точки 3 3 и 4 4 имеют r = 0 r=0, значит S 3 = { 3 } S3​={3}, S 4 = { 4 } S4​={4} — никаких связей они не требуют. Достаточно одного ребра 1  ⁣ −  ⁣ 2 1−2 стоимости d ( 1 , 2 ) = 1 d(1,2)=1; минимальная суммарная стоимость равна 1 1.

Во втором тесте S 1 = { 1 , 2 } S1​={1,2}, так как d ( 1 , 2 ) = 3 ≤ 5 d(1,2)=3≤5, а точка 3 3 далеко ( d ( 1 , 3 ) = 20 > ; 5 d(1,3)=20>;5). Точки 2 2 и 3 3 имеют r = 0 r=0 и собственных зон не задают. Нужно связать только точки 1 1 и 2 2 ребром стоимости d ( 1 , 2 ) = 3 d(1,2)=3, поэтому ответ — 3 3.

В третьем тесте обе точки имеют r = 0 r=0, поэтому S 1 = { 1 } S1​={1}, S 2 = { 2 } S2​={2} — никаких требований связности нет. Оптимальный лес пуст: S = 0 S=0 и рёбер не выбирается ( m = 0 m=0). Это иллюстрирует, что строка с рёбрами может отсутствовать, когда m = 0 m=0.
Ограничения

Ограничение времени
4 с
Ограничение памяти
272 МБ

Примеры
Пример 1
Ввод

3
4
0 0 1
0 1 1
5 0 0
5 1 0
3
0 0 5
3 0 0
10 10 0
2
0 0 0
1000000000 1000000000 0

Вывод

1
1
1 2
3
1
1 2
0
0

Solve it in very optimized version in c++