#include<bits/stdc++.h> #define int long long using namespace std; const int N=5e5+10,M=1145; int n,m,a[N],e[M][M],tp,fa[N],sz[N],t[N]; struct Node { int x,y,w; }s[M*M*2]; struct node { int num,w; }c[N]; bool cmp(Node x,Node y) { return x.w<y.w; } bool cmp1(node x,node y) { return x.w<y.w; } int findf(int x) { if(fa[x]==x) { return x; } fa[x]=findf(fa[x]); return fa[x]; } int hebing(int x,int y) { if(sz[x]>sz[y]) { swap(x,y); } fa[x]=y; sz[y]+=sz[x]; } int kk() { sort(s+1,s+1+tp,cmp); for(int i=1;i<=n;i++) { fa[i]=i; sz[i]=1; } int cnt=0; for(int i=1;i<=tp;i++) { Node now=s[i]; //cout<<now.x<<" "<<now.y<<" "<<now.w<<'\n'; int fx=findf(now.x),fy=findf(now.y); if(fx!=fy) { hebing(fx,fy); cnt+=now.w; } } return cnt; } signed main() { //freopen("graph.in","r",stdin); //freopen("graph.out","w",stdout); cin>>n>>m; if(n<=1000) { 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; e[x][y]=e[y][x]=z; } for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { if(!e[i][j]) { e[i][j]=min(a[i],a[j]); } s[++tp]=(Node){i,j,e[i][j]}; } } cout<<kk()<<"\n"; return 0; } for(int i=1;i<=n;i++) { cin>>a[i]; c[i]=(node){i,a[i]}; } sort(c+1,c+1+n,cmp1); map<int,int>mp; for(int i=1;i<=m;i++) { int x,y,z; cin>>x>>y>>z; s[++tp]=(Node){x,y,z}; mp[x*1e9+y]=mp[y*1e9+x]=1; } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(!mp[c[i].num*1e9+c[j].num]&&c[i].num!=c[j].num) { s[++tp]=(Node){c[i].num,c[j].num,min(c[i].w,c[j].w)}; break; } } } cout<<kk(); return 0; }