#HDR002C. 不想爬坡

不想爬坡

题目背景

数据已在赛后加强。

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

题目描述

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

输入格式

输入共 m2m+2 行。

第一行有两个整数 n,mn, m,表示图的节点数和边数。第二行有 nn 个整数,代表这 nn 个节点的海拔值 hih_i

第三行至第 m+2m+2 行每行各有三个整数 ui,vi,wiu_i,v_i,w_i,表示从 uiu_i 节点到 viv_i 节点有一条权值为 wiw_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

提示

第一个样例如下图所示:

3.png

注意到最短路径只有一条(124671\to 2 \to 4 \to 6 \to 7),因而只能走这条路。路径上海拔最高点为 66,最低为 22。因而在长度为 66 的路径中最小的海拔差为 149149

第二个样例如下图所示:

4.png

注意到该图中任意一条 1177 的路径均为最短路径。为了让路尽可能平缓,应该选择 1345(6)71\to 3 \to 4 \to 5(6) \to 7,因而路径上海拔最高点为 33(或 5,65,6),最低点为 11(或 4,74,7),此时最小的海拔差为 9999

数据规模与约定

本题采用捆绑测试。

对于 100%100\% 的数据,1n1×1041\leq n \leq 1\times 10^41m3×1041\leq m \leq 3\times 10^49×109hi9×109-9\times 10^9 \leq h_i \leq 9 \times 10^9,保证全图中任意简单路径长度均不超过 1×10181\times 10^{18},且均为非负权边。

Subtask1(10pts){\tt Subtask 1(10 pts)}:保证图中仅一条最短路。
Subtask2(40pts){\tt Subtask 2(40 pts)}1n1×1031\leq n \leq 1\times 10^3
Subtask3(50pts){\tt Subtask 3(50 pts)}:无特殊限制。