5368: Directed Minimum Spanning Tree
内存限制：256 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
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.
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≤T≤3000), denoting the number of test cases.
For each test case, the first line contains two integers n (1≤n≤105) and m (1≤m≤2×105), denoting the number of vertices and the number of edges in the graph.
Each of the next m lines contains three integers ui,vi,wi (1≤ui,vi≤n,1≤wi≤109), denoting the source, the target and the weight of the i-th edge. Please note that the edges are directed.
Let Sn and Sm be the sum of n and the sum of m in the input respectively. It is guaranteed that 1≤Sn≤5×105 and 1≤Sm≤106.
For each test case, the first line contains two integers n (1≤n≤105) and m (1≤m≤2×105), denoting the number of vertices and the number of edges in the graph.
Each of the next m lines contains three integers ui,vi,wi (1≤ui,vi≤n,1≤wi≤109), denoting the source, the target and the weight of the i-th edge. Please note that the edges are directed.
Let Sn and Sm be the sum of n and the sum of m in the input respectively. It is guaranteed that 1≤Sn≤5×105 and 1≤Sm≤106.
输出
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