2051 - 有负权边的最短路

题目描述

给定一个 n 个顶点,m 条边的有向图(其中某些边权可能为负,但保证没有负环)。请你计算从 1 号点到其他点的最短路(顶点从 1n 编号)。

输入

第一行两个整数 n,m

接下来的 m 行,每行有三个整数 u, v, l ,表示 uv 有一条长度为 l 的边。

数据范围

对于 10\% 的数据,n = 2m = 2

对于 30\% 的数据,n \le 5m \le 10

对于 100\% 的数据,1 \le n \le 200001 \le m \le 200000-10000 \le l \le 10000,保证从任意顶点都能到达其他所有顶点。

输出

n-1 行,第 i 行表示 1 号点到 i+1 号点的最短路。

样例

输入

3 3
1 2 -1
2 3 -1
3 1 2

输出

-1
-2
来源

图论 spfa

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1829
通过人数 947
金币数量 1 枚
难度 入门


上一题 下一题