该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

数据已在赛后加强。

今天懵哥正好没课，于是他就想骑车出去转一转，没想到在回来的路上居然自行车爆胎了……众所周知爆胎的自行车骑起来是很费劲的，但是他必须回去才能修车，所以他现在得找一条舒服点的路回去……

题目描述

懵哥现在处于一个有 $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$ 的双向边。

输出格式

输出共两行。

第一行为一个整数，代表最短路径长度。

第二也为一个整数，代表最小的最高、最低海拔的差值。

具体见下方样例。

样例

7 8
0 -50 99 0 99 99 0
1 2 1
2 4 2
1 3 2
3 4 2
4 5 2
4 6 1
5 7 2
6 7 2

6
149

7 8
0 -50 99 0 99 99 0
1 2 2
2 4 2
1 3 2
3 4 2
4 5 2
4 6 2
5 7 2
6 7 2

8
99

提示

第一个样例如下图所示：

注意到最短路径只有一条（$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 1\times 10^4$，$1\leq m \leq 3\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)}$：无特殊限制。