#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
#define up(i,j,k,l) for(int i=j;i<=k;i+=l)
#define down(i,j,k,l) for(int i=j;i>=k;i-=l)
using namespace std;
const int N=2e1+10;
int n,k;
int a[N][N];
int s,t;
int ut,vt;
void solve()
{
cin>>n>>k;
char u,v;
int w;
up(i,0,N-1,1){
up(j,0,N-1,1){
a[i][j]=INT_MAX;
}
}
up(i,1,n-1,1){
cin>>w;
a[i][i+1]=w;
a[i+1][i]=w;
}
cin>>w;
a[1][n]=w;
a[n][1]=w;
up(i,1,k,1){
cin>>u>>v>>w;
ut=u-'A'+1;
vt=v-'A'+1;
if(a[ut][vt]==INT_MAX){
a[ut][vt]=w;
a[vt][ut]=w;
}
else{
a[ut][vt]=max(a[ut][vt],w);
a[vt][ut]=max(a[vt][ut],w);
}
}
cin>>u>>v;
s=u-'A'+1;
t=v-'A'+1;
up(l,1,n,1){
up(i,1,n,1){
up(j,1,n,1){
a[i][j]=min(a[i][j],a[i][l]+a[l][j]);
}
}
}
cout<<a[s][t];
return;
}
int main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int _=1;
//cin>>_;
up(i,1,_,1){
solve();
}
return 0;
}