← 返回题目列表

Codeforces · 1764/F

F. 多蕾米的实验树

中文机器翻译题面 查看原题

Doremy 有一个边加权树,具有 $$$n$$$ 个顶点,其权重是 $$$1$$$ 和 $$$10^9$$$ 之间的整数。她对此进行了 $$$\frac{n(n+1)}{2}$$$ 实验。

在每个实验中,Doremy 选择顶点 $$$i$$$ 和 $$$j$$$ 使得 $$$j \leq i$$$ 并将它们直接与权重为 $$$1$$$ 的边连接起来。那么,图中恰好存在一个循环(或者当 $$$i=j$$$ 时为自循环)。 Doremy 将 $$$f(i,j)$$$ 定义为从每个顶点到循环的最短路径的长度之和。

形式上,令 $$$\mathrm{dis}_{i,j}(x,y)$$$ 为添加权重 $$$1$$$ 的边 $$$(i,j)$$$ 时顶点 $$$x$$$ 和 $$$y$$$ 之间的最短路径的长度,$$$S_{i,j}$$$ 为位于添加边 $$$(i,j)$$$ 时循环。然后,

$$$$$$ f(i,j)=\sum_{x=1}^{n}\left(\min_{y\in S_{i,j}}\mathrm{dis}_{i,j}(x,y)\right)。 $$$$$$

Doremy 写下 $$$f(i,j)$$$ 的所有值,使得 $$$1 \leq j \leq i \leq n$$$,然后进入睡眠状态。然而,醒来后,她发现那棵树不见了。幸运的是,$$$f(i,j)$$$ 的值仍在她的笔记本中,并且她知道它们属于哪个 $$$i$$$ 和 $$$j$$$。给定 $$$f(i,j)$$$ 的值,你能帮助她恢复树吗?

保证至少存在一棵合适的树。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2000$$$) — 树中的顶点数。

以下 $$$n$$$ 行包含一个下三角矩阵,第 $$$i$$$ 行上有 $$$i$$$ 整数;第 $$$i$$$ 行上的第 $$$j$$$ 整数是 $$$f(i,j)$$$ ($$$0 \le f(i,j) \le 2\cdot 10^{15}$$$)。

保证存在一棵树,其权重为 $$$1$$$ 和 $$$10^9$$$ 之间的整数,使得树的 $$$f(i,j)$$$ 的值与输入中给出的值匹配。

输出

打印描述树的 $$$n-1$$$ 行。在输出的第$$$i$$$行中,输出三个整数$$$u_i$$$、$$$v_i$$$、$$$w_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$1 \le w_i \le 10^9$$$),代表一条边$$$(u_i,v_i)$$$,其权重为$$$w_i$$$。

如果有多个答案,您可以输出任何一个。

所有边必须形成一棵树,并且 $$$f(i,j)$$$ 的所有值必须与输入中给出的值匹配。

示例

输入 #1

3
7
3 5
0 2 8

输出 #1

2 3 3
1 2 2

输入 #2

9
8081910646
8081902766 8081903751
8081902555 8081903540 8081905228
3090681001 3090681986 3090681775 7083659398
7083657913 7083658898 7083658687 2092437133 15069617722
1748216295 1748217280 1748217069 5741194692 749972427 10439821163
2377558289 2377559274 2377559063 6370536686 1379314421 5028071980 8866466178
1746983932 1746984917 1746984706 5739962329 748740064 10438588800 5026839617 10448447704
2341942133 2341943118 2341942907 6334920530 1343698265 4992455824 8830850022 4991223461 9115779270

输出 #2

1 2 985
2 3 211
2 4 998244353
2 5 998244853
4 6 671232353
6 8 1232363
4 7 356561356
7 9 35616156

注意

在第一个测试用例中,下图从左到右、从上到下分别显示了对$$$(1,1)$$$、$$$(1,2)$$$、$$$(1,3)$$$、$$$(2,2)$$$、$$$(2,3)$$$、$$$(3,3)$$$分别用边连接时的图形。黄色的节点位于循环上。