T560635 单源最短路径

## 题目描述 给定一个 $n$ 个节点，$m$ 条有向边的带负权图，规定一条路径的长度是这条路径上经过的所有边的边权之和，请你计算从节点 $1$ 出发，到每个节点的最短路径。 如果从节点 $1$ 出发无法到达某个节点，我们认为节点 $1$ 到这个节点的最短路径是无穷大；在存在负环的前提下，最短路径也有可能是无穷小。 ## 输入格式 第一行为两个个正整数 $n, m$。 第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。 - $1 \le n, m \le 2 \times 10^3$ - $1 \le u_i, v_i \le n$ - $-10^9 \le w_i \le 10^9$ ## 输出格式 输出一行 $n$ 个空格分隔的非负整数，表示 $1$ 到每个点的距离。如果 $1$ 到某个点的距离是无穷大，改为输出`INF` ；如果 $1$ 到某个点的距离是无穷小，改为输出`-INF` ## 样例输入 1 ``` 7 8 1 3 4 1 2 3 3 2 -2 2 4 -1 4 5 7 5 7 2 5 4 -10 6 7 -1 ``` ## 样例输出 1 ``` 0 2 4 -INF -INF INF -INF ```

无

无