我们维护(d[i,0/1])，其中(d[i,0])表示从1到(i)号结点经过路径中的最小值，(d[i,1])表示从(n)出发到(i)的最大值。之后可以考虑枚举中转站(i)，利用(d[i,1]-d[i,0])来更新答案即可。这样做的正确性就是这样可以覆盖所有的情况（肯定会经过一个中转站。
这里我用的dijkstra来对(d)数组进行维护。具体方法为：
假设我们现在求(d[i,0])，那么我们维护一个小根堆，之后像dijkstra那样转移就行了。因为当结点(u)被选出来时，(u)的前驱要么已经用来更新，要么其(dis)是大于(d[u])的。因此就可以知道，当某个结点去更新其它结点时，它不会再被其它结点重新更新，这样正确性就可以保证了。
对于(d[i,1])分析也同理，这时需要维护一个大根堆。就不赘述了。
代码如下：
#include <bits/stdc++.h>
#define mp make_pair
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5 + 5, M = 5e5 + 5;
int n, m;
int a[N] ;
struct mm{
int x, y, z;
}edges[N];
struct Edge{
int v, next;
}e[M << 1];
struct node{
int u, d;
bool operator < (const node &A) const {
return d > A.d;
}
};
int head[N], tot;
void adde(int u, int v) {
e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
}
int d[N][2];
bool vis[N] ;
void Dij1(int s, int p) {
memset(vis, 0, sizeof(vis)) ;
d[s][p] = a[s];
priority_queue <pair<int, int> > q;
q.push(mp(a[s], s)) ;
while(!q.empty()){
pair<int, int> now = q.top(); q.pop() ;
int u = now.second, dis = now.first;
if(vis[u]) continue ;
vis[u] = 1;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(d[v][p] < max(dis, a[v])) {
d[v][p] = max(dis, a[v]) ;
q.push(mp(d[v][p], v)) ;
}
}
}
}
void Dij2(int s, int p) {
memset(vis, 0, sizeof(vis)) ;
for(int i = 1; i <= n; i++) d[i][p] = INF;
d[s][p] = a[s];
priority_queue <node> q;
q.push(node{s, a[s]}) ;
while(!q.empty()){
node now = q.top(); q.pop() ;
int u = now.u, dis = now.d;
if(vis[u]) continue ;
vis[u] = 1;
for(int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(d[v][p] > min(dis, a[v])) {
d[v][p] = min(dis, a[v]) ;
q.push(node{v, d[v][p]}) ;
}
}
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
memset(head, -1, sizeof(head)); tot = 0;
for(int i = 1; i <= n; i++) cin >> a[i] ;
for(int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
edges[i] = mm{x, y, z} ;
adde(x, y) ;
if(z == 2) adde(y, x) ;
}
Dij2(1, 0);
memset(head, -1, sizeof(head)); tot = 0;
for(int i = 1; i <= m; i++) {
int x = edges[i].x, y = edges[i].y, z = edges[i].z ;
adde(y, x);
if(z == 2) adde(x, y) ;
}
Dij1(n, 1) ;
int ans = 0;
for(int i = 1; i <= n; i++)
ans = max(ans ,d[i][1] - d[i][0]) ;
cout << ans ;
return 0;
}