有的能过有的就不能过，很迷，调半天也不知道错在哪，过不了样例但是40pts

#include<bits/stdc++.h>
#define int long long int
#define db long double
#define endl '\n'
// #define st_it set<int>::iterator
// #define list_it list<int>::iterator
// #define itr ::iterator
// #define E 1e-6
#define MX LONG_LONG_MAX
// #define MN INT_MIN

using namespace std;

void Dji(int n,vector<vector<pair<int,int>>>& tu,vector<int>& dis){
	fill(dis.begin(),dis.end(),MX);
	vector<bool>vis(n+1);
	dis[1]=0;
	priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
	pq.push({0,1});
	while(!pq.empty()){
		int u=pq.top().second;
		pq.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(auto [v,w]:tu[u]){
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				pq.push({dis[v],v});
			}					
		}
	}
}

void solve(){
	int n,m;
	cin>>n>>m;
	vector<vector<pair<int,int>>> tu(n+1);
	vector<int>dian(n+1);
	vector<int>dis(n+1);
	for(int i=1;i<=n;i++) cin>>dian[i];
	while(m--){
		int u,v,w;
		cin>>u>>v>>w;
		tu[u].push_back({v,w+dian[u]});
		tu[v].push_back({u,w+dian[v]});		
	}
	Dji(n,tu,dis);
	cout<<dis[n]-dian[n];
}

signed main(){
	//ios::sync_with_stdio(0);
  //cin.tie(nullptr);
  int T;
  //cin>>T;
  T=1;
	while(T--) solve();
  return 0;
}