/*

*/
#define method_2
#ifdef method_1
/*

无剪枝 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,m;
int die[maxn];//每个节点的崩塌时间 
int G[maxn][maxn];
int ans=INF;
int vis[maxn];
void dfs(int x,int now){ //在x节点处 且目前时刻为now 
    if(now>=die[x]){ //不能在毁灭时刻及以后时刻到达 
        return;
    }
    if(x==n){
        ans=min(ans,now);
        return;
    }
//  if(now>=ans) return; //剪枝 
    for(int i=1;i<=n;i++){
        if(!vis[i]&&G[x][i]!=INF){
            dfs(i,now+G[x][i]);
            vis[i]=0; //回溯 
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    freopen("偷拍硕哥1.in","r",stdin);
    memset(vis,0,sizeof(vis));
    memset(G,INF,sizeof(G));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>die[i];
    }
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        G[a][b]=min(G[a][b],c);
        G[b][a]=G[a][b];
    }
    dfs(1,0);
    if(ans==INF) cout<<-1;
    else cout<<ans;
    return 0;
}
#endif
#ifdef method_2
/*

有剪枝 
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,m;
int die[maxn];//每个节点的崩塌时间 
int G[maxn][maxn];
int ans=INF;
int vis[maxn];
void dfs(int x,int now){ //在x节点处 且目前时刻为now 
    if(now>=die[x]){ //不能在毁灭时刻及以后时刻到达 
        return;
    }
    if(x==n){
        ans=min(ans,now);
        return;
    }
    if(now>=ans) return; //剪枝 
    for(int i=1;i<=n;i++){
        if(!vis[i]&&G[x][i]!=INF){
            dfs(i,now+G[x][i]);
            vis[i]=0; //回溯 
        }
    }
}
int main() {
    ios::sync_with_stdio(false); 
//  freopen("偷拍硕哥1.in","r",stdin);
    memset(vis,0,sizeof(vis));
    memset(G,INF,sizeof(G));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>die[i];
    }
    int a,b,c;
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        G[a][b]=min(G[a][b],c);
        G[b][a]=G[a][b];
    }
    dfs(1,0);
    if(ans==INF) cout<<-1;
    else cout<<ans;
    return 0;
}
#endif
#ifdef method_3
/*

*/

#endif

/*

/
#define method_2
#ifdef method_1
/

无剪枝
/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,m;
int die[maxn];//每个节点的崩塌时间
int G[maxn][maxn];
int ans=INF;
int vis[maxn];
void dfs(int x,int now){ //在x节点处 且目前时刻为now
if(now>=die[x]){ //不能在毁灭时刻及以后时刻到达
return;
}
if(x==n){
ans=min(ans,now);
return;
}
// if(now>=ans) return; //剪枝
for(int i=1;i<=n;i++){
if(!vis[i]&&G[x][i]!=INF){
dfs(i,now+G[x][i]);
vis[i]=0; //回溯
}
}
}
int main() {
ios::sync_with_stdio(false);
freopen("偷拍硕哥1.in","r",stdin);
memset(vis,0,sizeof(vis));
memset(G,INF,sizeof(G));
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>die[i];
}
int a,b,c;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
G[a][b]=min(G[a][b],c);
G[b][a]=G[a][b];
}
dfs(1,0);
if(ans==INF) cout<<-1;
else cout<<ans;
return 0;
}
#endif
#ifdef method_2
/

有剪枝
/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=100+5;
const int INF=0x3f3f3f3f;
int n,m;
int die[maxn];//每个节点的崩塌时间
int G[maxn][maxn];
int ans=INF;
int vis[maxn];
void dfs(int x,int now){ //在x节点处 且目前时刻为now
if(now>=die[x]){ //不能在毁灭时刻及以后时刻到达
return;
}
if(x==n){
ans=min(ans,now);
return;
}
if(now>=ans) return; //剪枝
for(int i=1;i<=n;i++){
if(!vis[i]&&G[x][i]!=INF){
dfs(i,now+G[x][i]);
vis[i]=0; //回溯
}
}
}
int main() {
ios::sync_with_stdio(false);
// freopen("偷拍硕哥1.in","r",stdin);
memset(vis,0,sizeof(vis));
memset(G,INF,sizeof(G));
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>die[i];
}
int a,b,c;
for(int i=1;i<=m;i++){
cin>>a>>b>>c;
G[a][b]=min(G[a][b],c);
G[b][a]=G[a][b];
}
dfs(1,0);
if(ans==INF) cout<<-1;
else cout<<ans;
return 0;
}
#endif
#ifdef method_3
/

*/

#endif