题目描述

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

输入格式

第一行两个整数 $n,m$。

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

输出格式

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

样例

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

-1
-2

数据范围

对于 $10\%$ 的数据：$n=2$，$m=2$

对于 $30\%$ 的数据：$n\le 5$，$m\le 10$

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

来源

图论 SPFA