【题解】：
最短路径问题，保证距离最短的同时，学妹权值最大，哈哈
【code】：
#include<iostream>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<stdlib.h> #define N 50005
#define INF 100000000
using namespace std; struct Edge
{
int to;
int next;
int w;
int num;
}edge[N<<]; struct Nod
{
int u;
int dis;
int num;
}now,temp; bool operator< (Nod a,Nod b)
{
if(a.dis!=b.dis)
return a.dis>b.dis;
return a.num<b.num;
} int weight[N],head[N],visit[N];
int dis[N];
int ans[N]; void init(int n)
{
int i;
for(i=;i<=n;i++)
{
visit[i] = ;
dis[i] = INF;
head[i] = -;
ans[i]=-;
}
} void Dijkstra(int s)
{
int i,v;
dis[s] = ;
ans[s] = weight[s];
priority_queue<Nod> p_q;
temp.dis = ;
temp.u = s;
temp.num = weight[s];
p_q.push(temp);
while(!p_q.empty())
{
temp = p_q.top();
p_q.pop();
if(visit[temp.u]) continue;
visit[temp.u] = ;
for(i=head[temp.u];i!=-;i=edge[i].next)
{
v = edge[i].to;
if(!visit[v])
{
if(dis[v]>dis[temp.u]+edge[i].w||(dis[v]!=INF&&dis[v]==dis[temp.u]+edge[i].w&&ans[v]<ans[temp.u]+weight[v]))
{
dis[v] = dis[temp.u]+edge[i].w;
ans[v] = ans[temp.u]+weight[v];
now.u = v;
now.dis = dis[v];
now.num = ans[v]; p_q.push(now);
}
}
}
}
} int main()
{
int m,n;
while(~scanf("%d%d",&n,&m))
{
int i;
for(i=;i<n;i++) scanf("%d",weight+i);
int id = ;
init(n);
int a,b,c;
for(i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
a--,b--;
edge[id].to = b;
edge[id].w = c;
edge[id].next = head[a];
head[a] = id++; //将边 a --> b保存 edge[id].to = a;
edge[id].w = c;
edge[id].next = head[b];
head[b] = id++; //将边 b --> a保存
}
Dijkstra();
printf("%d\n",ans[n-]);
}
return ;
}