Directed Minimum Spanning Tree

Yukikaze is studying graph theory. She is fascinated by an interesting combinatorial optimization problem, called the Directed Minimum Spanning Tree Problem.

A subgraph $T$ of a directed graph $G=(V,E)$ is called a Spanning Tree rooted at $r$ if for every vertex $v$ in $V-\{r\}$, there is exactly one path in $T$ from $r$ to $v$. The weight of a Spanning Tree is the sum of the weights of its edges. The Directed Minimum Spanning Tree (DMST) rooted at $r$ is the Spanning Tree rooted at $r$ which has the minimal weight.

For every vertex $u$ in the given graph, Yukikaze wants you to find the weight of the Directed Minimum Spanning Tree rooted at vertex $u$.

The input consists of several test cases. The first line of the input contains a single integer $T$ $(1 \leq T \leq 3000)$, denoting the number of test cases.

For each test case, the first line contains two integers $n$ $(1 \leq n \leq 10^5)$ and $m$ $(1 \leq m \leq 2 \times 10^5)$, denoting the number of vertices and the number of edges in the graph.

Each of the next $m$ lines contains three integers $u_i,v_i,w_i\ (1 \leq u_i, v_i \leq n, 1 \leq w_i \leq 10^9)$, denoting the source, the target and the weight of the $i$-th edge. Please note that the edges are directed.

Let $S_n$ and $S_m$ be the sum of $n$ and the sum of $m$ in the input respectively. It is guaranteed that $1 \leq S_n \leq 5 \times 10^5$ and $1 \leq S_m \leq 10^6$.

For each test case, output $n$ lines. The $i$-th line should contain the weight of the Directed Minimum Spanning Tree rooted at vertex $i$. If such DMST doesn't exist, output $-1$.

2
5 6
1 2 5
2 3 6
3 1 7
1 4 3
4 5 4
5 1 2
6 8
1 4 1
2 5 7
4 3 4
5 6 12
6 2 9
3 5 10
3 1 23
4 2 17

18
20
19
17
16
36
-1
55
58
-1
-1

2021“MINIEYE杯”中国大学生算法设计超级联赛（4）