B3602 [图论与代数结构 202] 最短路问题_2

给定一张 $n$ 个点、$m$ 条边的有向图，求 $1$ 号点到每个点的最短路径长度。 **注意，图可能存在重边和自环。**

第一行两个整数 $n, m$。 接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$。表示一条从 $u_i$ 到 $v_i$ 长度为 $w_i$ 的有向边。

一行 $n$ 个整数，第 $i$ 个整数表示 $1$ 到 $i$ 的最短路径长度，如果不存在从 $1$ 到 $i$ 的路径则第 $i$ 个整数用 $-1$ 替代。

本题没有部分分。 对于所有数据，$1\leq n,m \leq 3\times 10^5$，$1\leq w_i\leq 10^9$。 请注意答案上界的大小，可能需要使用 C++ 中的 `long long int` 类型。