题面翻译

流行乐队“Flayer”将在 $n$ 个城市开演唱会，这 $n$ 个城市的人都想去听演唱会。每个城市的票价不同，于是这些人就想是否能去其他城市听演唱会更便宜（去要路费的，而且需要返程，可以描述为 $\min\limits_{j=1}^n 2d(i,j)+a_j$）

输入格式：

第一行包含两个整数 $n$ 和 $m$。

接下来 $m$ 行，每行三个数 $u,v,k$，表示 $u$ 城市到 $v$ 城市要 $k$ 元。

接下来 $n$ 个数，表示每个城市的票价。

简要题意

给出一个 $n$ 个点 $m$ 条边的带权无向图。定义 $d(i, j)$ 为两点之间最短路长度。每个点还有个点权 $a_{i}$ 。现在对于图中的每个点 $i$ , 你都需要计算:

$\min _{j=1}^{n}\left\{2 d(i, j)+a_{j}\right\}$

$1 \leq n, m \leq 10^{5}$