生命

给定一张图，有 \(n\) 个点 \(m\) 条双向边组成，DD 目前在 \(1\) 号点上要到 \(n\) 号点去，这 \(n\) 个点中有一些点上有机器人，机器人和 DD 的速度都是每秒可以走一个单位长度，这些机器人都是 AI 操控采取最优策略来拦截 DD，DD 每碰到一个机器人就会扣一滴生命值（一个点上碰到 \(x\) 个就扣 \(x\) 滴生命值），她想知道从 \(1\) 号点到 \(n\) 号点最少要扣多少生命值。

输入格式
第一行两个整数分别表示 \(n,m\)

第二行 \(n\) 个整数，\(a_i\)表示 \(i\) 号点上有 \(a_i\)个机器人
接下来 \(m\) 行，每行三个整数，分别表示该边的起点、终点和长度

输出格式
输出最少要扣多少生命值

数据范围
对于 \(30\%\) 的数据，\(2 \leq n \leq 10, 1 \leq m \leq 20\)

对于 \(50\%\) 的数据, \(2 \leq n \leq 500, 1 \leq m \leq 1000\)

对于\(100\%\)的数据，\(1 \leq u_i,v_i \leq n, 2 \leq n \leq 10^5,1 \leq m \leq 5*10^5,1 \leq dis_i,a_i \leq 10^9\)
输出时每行末尾的多余空格，不影响答案正确性

样例输入

4 6
1 2 3 4 
1 2 1
2 3 2
3 4 1 
1 4 2
2 4 10
4 4 3

样例输出

8

首先如果一个机器人在中途跟上了他，那么机器人可以一路跟到终点再杀他。因为和DD速度相同，所以他们的最优策略均是直奔终点。

那么方法就很明确了。求出从1号点到n号点的最短路和n号点到其他点的最短路，然后如果有机器人的最短路小于等于DD的最短路，那么DD逃不过这些机器人的伤害

#include 
using namespace std;
const int N=1e5+5,M=5e5+5;
struct node{
    int v;
    long long w;
    bool operator<(const node&n)const{
        return w>n.w;
    }
};
int n,m,k;
vectorg[N];
long long p;
int a[N];
long long dis[N];
priority_queuepq;
bool vis[N];
long long ans;
void dijkstra(int s)
{
    pq.push((node){s,0});
    dis[s]=0;
    while(!pq.empty())
    {
        k=pq.top().v;
        pq.pop();
        if(vis[k])
            continue;
        vis[k]=1;
        for(int i=0;i>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",a+i);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%lld",&u,&v,&w);
        g[u].push_back((node){v,w});
        g[v].push_back((node){u,w});
    }
    memset(dis,1,sizeof(dis));
    dijkstra(1);
    p=dis[n];
    memset(dis,1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dijkstra(n);
    for(int i=1;i<=n;i++)
        if(dis[i]<=p)
            ans+=a[i];
    cout<