农场主约翰的农场由 n 个牧场组成，牧场之间由单向道路相连。每条路都有一个权重，代表从起点到终点所需的时间。道路的权重可能为负数，即奶牛走得太快，导致时间倒流！但是，农场主约翰保证，奶牛不可能陷入时间循环，它们可以通过穿越一连串的道路无限地回到过去。而且，每对牧场在每个方向上最多只有一条路相连
给你一个长度为 $n$ 的序列 $\{d\}$，你需要构造一个有向带权，使得点 $1$ 到点 $i$ 的最短路长度为 $d_i$，同时使得所有边的边权之和尽可能小。

第一行是t（1<=t<=10⁵)，然后是t个测试样例
每个测试用例的第一行都包含一个整数 n ( 1≤n≤10⁵ ) --牧场数量。
每个测试用例的第二行包含 n 个空格分隔的整数 d1,d2,…,dn( 0≤di≤10⁹ ) - 数组 d 。保证 d1=0 。

针对每个测试用例，输出符合约翰农场主记忆的农场的最小可能成本。

图中不能出现负环和重边。
在第一个测试案例中，可以添加道路

从牧场 1到牧场 2，用时 2
从牧场 2到牧场 3，耗时 1
从牧场 3到牧场 1，时间为 −3
从牧场 3到牧场 2，时间为 −1
从牧场 2到牧场 1，时间为 −2。
总费用为 2+1+−3+−1+−2=−3。

在第二个测试案例中，可以添加一条从牧场 1到牧场 2的道路，耗时 1000000000；添加一条从牧场 2到牧场 1的道路，耗时 −1000000000。总费用为 1000000000+−1000000000=0 。

在第三个测试案例中，不能添加任何道路。总成本为 0。

 大数据与人工智能学院暑假练习验收(第二场)