Bitgard 是一个繁华的大都市。目前，它恰好有 $n$ 个交叉路口（编号为 $1$ 到 $n$），由 $m$ 条单向道路连接。每条道路都有一个非负的长度。道路相交的唯一地点是交叉路口，尽管可能存在许多隧道和高架桥。已知从 $1$ 号交叉路口可以到达每个交叉路口，但并不一定每个交叉路口都能从其他任意交叉路口到达。

Bitgard 扩张和富裕得如此之快，以至于有些人开始对抢劫其设施产生兴趣。其中两个这样的人是 Bolek 和 Lolek。为了达到他们的目的，他们搬到了 $1$ 号交叉路口，现在他们想抢劫另一个交叉路口附近的商店。如果他们决定袭击第 $i$ 个交叉路口附近的商店，为了尽量减少彼此之间产生关联的风险，他们将通过两条边不相交的路径前往该交叉路口。如果存在这样的路径，Bolek 和 Lolek 想知道这些路径长度之和的最小值。

对于除第一个交叉路口以外的每个交叉路口，帮助 Bolek 和 Lolek 确定该值，或者指出无法找到两条这样的路径。

输入格式

第一行给出一个整数 $Z \le 100$，表示接下来的行中描述的测试用例数量。

每个测试用例的第一行包含两个整数 $n$ 和 $m$，分别表示 Bitgard 中的交叉路口数量和单向道路数量。

接下来的 $m$ 行中，每行包含一条道路的描述。第 $i$ 行包含三个整数 $a_i, b_i$ 和 $c_i$（$a_i \ne b_i \in [1, n], c_i \in [0, 10^9]$），表示有一条起点为交叉路口 $a_i$、终点为交叉路口 $b_i$ 且长度为 $c_i$ 的道路。你可以认为对于每对有序交叉路口，最多只有一条道路连接它们。

所有测试用例的参数 $n$ 和 $m$ 的总和分别不超过 $10^5$ 和 $10^6$。

输出格式

每个测试用例的输出应包含一行，由 $n - 1$ 个（可能为零个）数字组成，表示除第一个交叉路口外所有交叉路口的结果。如果可以找到从顶点 $1$ 到顶点 $i$ 的两条边不相交的路径，则对应第 $i$ 个顶点的数字应等于这些路径长度之和的最小值。否则，对于该交叉路口，你应该输出 -1。

样例

输入样例 1

3
3 4
1 2 1
1 3 2
2 3 3
3 2 4
2 2
1 2 1
2 1 0
5 7
1 2 4
2 3 3
1 3 8
3 5 3
4 5 2
5 4 7
1 5 1

输出样例 1

7 6
-1
-1 15 -1 11

输入样例 2

2
4 9
1 2 18
2 3 1
3 4 11
4 3 2
4 1 30
3 1 24
3 2 22
1 3 18
2 4 1
4 5
1 2 2
1 3 14
1 4 4
2 1 20
2 3 30

输出样例 2

58 37 48
-1 46 -1