考虑使用费用流。把一个点拆成两个，表示入和出，因为每个点要被恰好经过一次，所以每个点都应该是进一次，出一次，那么 \(s\) 向所有出点连边，费用为 \(0\)，流量为 \(1\)，所有入点向 \(t\) 连边，费用为 \(0\)，流量为 \(1\)。
然后把移动考虑进来。瞬移相当于直接进入某个点，所以 \(s\) 向所有入点连边，费用为瞬移的代价，流量为 \(1\)。对于一条边 \((u,v,w)\)，编号小的出点向编号大的入点连边，费用为 \(w\)，流量为 \(1\)。
建完图，直接跑费用流即可。
代码
/*
Luogu P2469 [SDOI2010] 星际竞速
2026-03-25
*/
#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
template<int maxn,int maxm>class LSQXX{
public:int head[maxn],nxt[maxm*2],to[maxm*2],val[maxm*2],cost[maxm*2],cnt=1;void add(int u,int v,int w,int c){nxt[++cnt]=head[u],to[cnt]=v,val[cnt]=w,cost[cnt]=c,head[u]=cnt;}void clear(){cnt=0;memset(head,0,sizeof(head));}
};
const int maxn=810,maxm=15010,inf=1000000000;
int n,m,a[maxn];
class Network_Flow{
private:LSQXX<maxn*2,maxn*4+maxm>e;bool vis[maxn*2],inque[maxn*2];int dis[maxn*2],s,t,ans,cur[maxn*2];queue<int>q;bool spfa(){for(int i=s;i<=t;i++) dis[i]=inf;dis[s]=0;q.push(s);while(!q.empty()){int u=q.front();q.pop();inque[u]=0;for(int i=e.head[u];i;i=e.nxt[i]){int v=e.to[i];if(!e.val[i]) continue;if(dis[v]<=dis[u]+e.cost[i]) continue;dis[v]=dis[u]+e.cost[i];if(!inque[v]) inque[v]=1,q.push(v);}}return dis[t]!=inf;}int dfs(int u,int flow=inf){if(u==t||flow==0) return flow;if(vis[u]) return 0;vis[u]=1;int sum_flow=0;for(int&i=cur[u];i;i=e.nxt[i]){int v=e.to[i];if(dis[v]!=dis[u]+e.cost[i]) continue;int nflow=dfs(v,min(flow,e.val[i]));e.val[i]-=nflow,e.val[i^1]+=nflow;sum_flow+=nflow,flow-=nflow;ans+=nflow*e.cost[i];if(flow==0) break;}vis[u]=0;return sum_flow;}void edge_add(int u,int v,int w,int c){e.add(u,v,w,c),e.add(v,u,0,-c);}int bh(int u,int x){return (u<<1)+x-1;}
public:int work(){while(spfa()){for(int i=s;i<=t;i++) cur[i]=e.head[i];dfs(s);}return ans;}void build(){s=0,t=(n<<1)+3;for(int i=1;i<=n;i++) edge_add(s,bh(i,1),1,a[i]),edge_add(s,bh(i,0),1,0),edge_add(bh(i,1),t,1,0);for(int i=1;i<=m;i++){int u,v,w;read(u,v,w);if(u>v) swap(u,v);edge_add(bh(u,0),bh(v,1),1,w);}}
}wll;
signed main(){read(n,m);for(int i=1;i<=n;i++) read(a[i]);wll.build();write(wll.work());return 0;
}