T197746 不想爬坡

**已在赛后加强数据。** Subtask 2 和 Subtask 3 的前 5 个测试点为加强数据。如果还出现错解通过的情况请联系 [Macesuted](/user/98482)。 今天懵哥正好没课，于是他就想骑车出去转一转，没想到在回来的路上居然自行车爆胎了……众所周知爆胎的自行车骑起来是很费劲的，但是他必须回去才能修车，所以他现在得找一条舒服点的路回去……

懵哥现在处于一个有 $n$ 个节点、$m$ 条边的无向图上，他现在正在 $1$ 号节点，终点位于 $n$ 号节点。每个节点有一个海拔值 $h_i$，每条边也有一个权值 $u_i$ 。他希望走的总路程最短，在总路程相同时路不要太颠簸，也就是说，他所选择的路径上海拔最高和海拔最低点的**海拔差值**也最小。请你帮他求出这个最短距离以及这样的路径上的海拔最低、最高点的海拔差值。

输入共 $m＋2$ 行。 第一行有两个整数 $n, m$，表示图的节点数和边数。第二行有 $n$ 个整数，代表这 $n$ 个节点的海拔值 $h_i$。 第三行至第 $m+2$ 行每行各有三个整数 $u_i, v_i, w_i$，表示从 $u_i$ 节点到 $v_i$ 节点有一条权值为 $w_i$ 的双向边。

输出共两行。 第一行为一个整数，代表最短路径长度。 第二也为一个整数，代表最小的最高、最低海拔的差值。 具体见下方样例。

第一个样例如下图所示：  注意到最短路径只有一条（$1\to 2 \to 4 \to 6 \to 7$），因而只能走这条路。路径上海拔最高点为 $6$，最低为 $2$。因而在长度为 $6$ 的路径中最小的海拔差为 $149$。 第二个样例如下图所示：  注意到该图中任意一条 $1$ 到 $7$ 的路径均为最短路径。为了让路尽可能平缓，应该选择 $1\to 3 \to 4 \to 5(6) \to 7$，因而路径上海拔最高点为 $3$（或 $5,6$），最低点为 $1$（或 $4,7$），此时最小的海拔差为 $99$。 ## 数据规模与约定 **本题采用捆绑测试。** 对于 $100\%$ 的数据，$1\leq n \leq 5\times 10^3$，$1\leq m \leq 2\times 10^4$，$-9\times 10^9 \leq h_i \leq 9 \times 10^9$，保证全图中任意简单路径长度均不超过 $1\times 10^{18}$，且均为非负权边。 ${\tt Subtask 1(10 pts)}$：保证图中仅一条最短路。 ${\tt Subtask 2(40 pts)}$：$1\leq n \leq 1\times 10^3$。 ${\tt Subtask 3(50 pts)}$：无特殊限制。