Doremy's Experimental Tree
Doremy has an edge-weighted tree with $$$n$$$ vertices whose weights are integers between $$$1$$$ and $$$10^9$$$. She does $$$\frac{n(n+1)}{2}$$$ experiments on it.In each experiment, Doremy chooses vertices $$$i$$$ and $$$j$$$ such that $$$j \leq i$$$ and connects them directly with an edge with weight $$$1$$$. Then, there is exactly one cycle (or self-loop when $$$i=j$$$) in the graph. Doremy defines $$$f(i,j)$$$ as the sum of lengths of shortest paths from every vertex to the cycle.Formally, let $$$\mathrm{dis}_{i,j}(x,y)$$$ be the length of the shortest path between vertex $$$x$$$ and $$$y$$$ when the edge $$$(i,j)$$$ of weight $$$1$$$ is added, and $$$S_{i,j}$$$ be the set of vertices that are on the cycle when edge $$$(i,j)$$$ is added. Then,$$$$$$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right). $$$$$$Doremy writes down all values of $$$f(i,j)$$$ such that $$$1 \leq j \leq i \leq n$$$, then goes to sleep. However, after waking up, she finds that the tree has gone missing. Fortunately, the values of $$$f(i,j)$$$ are still in her notebook, and she knows which $$$i$$$ and $$$j$$$ they belong to. Given the values of $$$f(i,j)$$$, can you help her restore the tree?It is guaranteed that at least one suitable tree exists.
In the first test case, the picture below, from left to right, from top to bottom, shows the graph when pairs $$$(1,1)$$$, $$$(1,2)$$$, $$$(1,3)$$$, $$$(2,2)$$$, $$$(2,3)$$$, $$$(3,3)$$$ are connected with an edge, respectively. The nodes colored yellow are on the cycle.
The first line of input contains a single integer $$$n$$$ ($$$2 \le n \le 2000$$$) — the number of vertices in the tree.The following $$$n$$$ lines contain a lower-triangular matrix with $$$i$$$ integers on the $$$i$$$-th line; the $$$j$$$-th integer on the $$$i$$$-th line is $$$f(i,j)$$$ ($$$0 \le f(i,j) \le 2\cdot 10^{15}$$$).It is guaranteed that there exists a tree whose weights are integers between $$$1$$$ and $$$10^9$$$ such that the values of $$$f(i,j)$$$ of the tree match those given in the input.
Print $$$n-1$$$ lines describing the tree. In the $$$i$$$-th line of the output, output three integers $$$u_i$$$, $$$v_i$$$, $$$w_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$1 \le w_i \le 10^9$$$), representing an edge $$$(u_i,v_i)$$$ whose weight is $$$w_i$$$.If there are multiple answers, you may output any.All edges must form a tree and all values of $$$f(i,j)$$$ must match those given in the input.
from collections import defaultdict

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        group_members = defaultdict(list)
        for member in range(self.n):
            group_members[self.find(member)].append(member)
        return group_members
from sys import stdin
input = lambda : stdin.readline()[:-1]

def solve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    edges = []
    for i in range(n):
        for j in range(i):
            d = A[i][i] + A[j][j] - 2 * A[i][j]
            if d % n == 0:
                d //= n
                edges.append(d * n * n + i * n + j)
    edges.sort()
    UF = UnionFind(n)
    for tmp in edges:
        d = tmp // (n * n)
        ij = tmp - n * n * d
        i = ij // n
        j = ij - n * i
        if UF.union(i, j):
            print(i + 1, j + 1, d)
solve()
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group = n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        self.group -= 1
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return self.group

    def all_group_members(self):
        dic = {r: [] for r in self.roots()}
        for i in range(self.n):
            dic[self.find(i)].append(i)
        return dic

    def __str__(self):
        return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

def solve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    edges = []
    for i in range(n):
        for j in range(i):
            d = A[i][i] + A[j][j] - 2 * A[i][j]
            if d % n == 0:
                d //= n
                edges.append(d * n * n + i * n + j)
    edges.sort()
    UF = UnionFind(n)
    for tmp in edges:
        d = tmp // (n * n)
        ij = tmp - n * n * d
        i = ij // n
        j = ij - n * i
        if UF.union(i, j):
            print(i + 1, j + 1, d)
T = 1
for t in range(1, T + 1):
    solve()
class UnionFind:

    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.group = n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        self.group -= 1
        if self.parents[x] > self.parents[y]:
            (x, y) = (y, x)
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for (i, x) in enumerate(self.parents) if x < 0]

    def group_count(self):
        return self.group

    def all_group_members(self):
        dic = {r: [] for r in self.roots()}
        for i in range(self.n):
            dic[self.find(i)].append(i)
        return dic

    def __str__(self):
        return '\n'.join(('{}: {}'.format(r, self.members(r)) for r in self.roots()))

def solve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    edges = []
    for i in range(n):
        for j in range(i):
            d = A[i][i] + A[j][j] - 2 * A[i][j]
            if d % n == 0:
                d //= n
                edges.append(d * n * n + i * n + j)
    edges.sort()
    UF = UnionFind(n)
    for tmp in edges:
        d = tmp // (n * n)
        ij = tmp - n * n * d
        i = ij // n
        j = ij - n * i
        if UF.union(i, j):
            print(i + 1, j + 1, d)
T = 1
for t in range(1, T + 1):
    solve()