题目描述

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

输入

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

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

数据范围

对于 $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$ ，保证从任意顶点都能到达其他所有顶点。

输出

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

样例

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

-1
-2

来源

图论 spfa