code in c++

Problem Alice is a curious person and comes up with a problem for Bob to solve. There is a graph G that has N nodes, numbered from I to N. Denote the shortest path distance between a pair of nodes u, vas s(u, v). Given the length of the shortest path between all pairs of nodes, check if it is possible to construct a tree with non-negative edge weights that satisfies the shortest path criteria. Input The first line contains the number of problems Alice wants Bob to solve: P. For each problem: The first line contains an integer - N-the number of nodes. Nlines follow. The the i-th line contains N space-separated integers denoting the shortest path from node i to all N nodes from Ito N. The j-th integer in the line denotes sati), and S(1:1) = 0. It is guaranteed that the given graph is connected. Output For each problem: If there exists a valid tree that satisfies the shortest path criteria, print 1. Print N-1 lines each containing 3 space-separated integers: u vw-representing the endpoints of the edge (u, v) (-indexed) and its weight respectively. You can print any valid tree that satisfies the given criteria. You can print any valid tree that satisfies the given criteria. Otherwise, if the there is no valid tree, print 0. Constraints 1