[R31E]翻转 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个包含 $n$ 个顶点和 $m$ 条边的简单有向图。每条边 $u \to v$ 都有一个翻转代价 $w$，表示将这条边翻转成 $v \to u$ 所需的代价。同时保证，如果存在边 $u \to v$，则一定不存在反向边 $v \to u$。

你可以执行任意次翻转操作：每次选择一条边 $u \to v$，支付其翻转代价 $w$，将其方向翻转成 $v \to u$。总成本是所有翻转操作的代价的和。

对于每个顶点 $i$（从 $1$ 到 $n$），你需要回答：最少需要多少代价，才能使得图中存在一个包含顶点 $i$ 的有向环？如果不可能，答案为 $-1$。

格式

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示顶点和边的数量。

接下来 $m$ 行，每行包含三个整数 $u, v, w$，表示存在一条从 $u$ 到 $v$ 的有向边，其翻转代价为 $w$。

输出格式

输出一行，包含 $n$ 个用空格分隔的整数。第 $k$ 个整数表示要形成一个包含顶点 $k$ 的环路所需的最小成本。如果不可能，则输出 $-1$。

样例

样例输入 #1

5 5
1 2 1
3 2 1
4 3 1
4 5 1
5 1 1

样例输出 #1

2 2 2 2 2

样例输入 #2

6 9
6 1 1
5 6 2
5 4 3
2 3 4
4 3 5
1 3 6
4 1 7
4 2 8
5 2 9

样例输出 #2

3 5 5 3 3 3

数据规模

对于 $20\%$ 的数据，$1\leq n \leq 10$。

对于 $40\%$ 的数据，$1 \leq n \leq 20$。

对于 $100\%$ 的数据，$1 \leq n \leq 100$，$1 \leq m \leq \frac{n \times (n-1)}{2}$，$1 \leq w_i \leq 10^9$，$1 \leq u, v \leq n$，且 $u \neq v$。

本题有附加分（$1$ 分）。对于附加分， $1 \leq n \leq 200$，其余条件与上方相同。