题目描述

给出一个 $n$ 个点、$m$ 条边的有向图，边权均为非负整数。请你求出从 $1$ 号点出发到每个点的最短路径长度。

输入格式

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

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

图中可能有重边和自环。

输出格式

输出一行 $n$ 个整数，第 $i$ 个数表示从 $1$ 号点到 $i$ 号点的最短路径长度；若无法到达则输出 $-1$。

相邻两个数之间用一个空格隔开。

输入输出样例 #1

输入 #1

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

输出 #1

0 1 3 6

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^5$，$0\le m\le 3\times 10^5$，$1\le u,v\le n$，$0\le w\le 10^9$。