#6 EA了，求调

#include <bits/stdc++.h>//only my railgun
#define int long long
using namespace std;
const int AC=114514;
const int INF=9223372036854775807;
int n,m,k,head[AC],vis[AC],dis[AC];
int e[1001][1001],siz[1001];
queue<int> q;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

inline void dijkstra(int a,int b){
	dis[a]=0;
	q.push(a);
	while(!q.empty()){
		int fr=q.front();q.pop();vis[fr]=0;
		for(int i=1;i<=100;i++){
			if(e[fr][i]==-1) continue;
			if(dis[i]>=dis[fr]+e[fr][i]){
				dis[i]=dis[fr]+e[fr][i];
				if(!vis[i]){
					q.push(i);
					vis[i]=1;
				}
			}
		}
	}
}

signed main(){
	n=read(),m=read();
	for(int i=1;i<=100;i++){
		for(int j=1;j<=100;j++) e[i][j]=-1;
	}
	for(int i=1;i<=n;i++) dis[i]=INF;
	for(int i=1;i<=n;i++){
		int w=read();
		if(i==n){
			e[i][1]=max(e[i][1],w);siz[i]=max(e[i][1],siz[i]);
			e[1][i]=max(e[1][i],w);siz[1]=max(e[1][i],siz[i]);
		}
		else{
			e[i+1][i]=max(e[i+1][i],w);siz[i+1]=max(e[i+1][i],siz[i+1]);
			e[i][i+1]=max(e[i][i+1],w);siz[i]=max(e[i][i+1],siz[i]);
		}
	}
	for(int i=1;i<=m;i++){
		char u,v;
		int w;
		cin>>u>>v;w=read();
		e[u-'A'+1][v-'A'+1]=max(e[u-'A'+1][v-'A'+1],w);siz[u-'A'+1]=max(e[u-'A'+1][v-'A'+1],siz[u-'A'+1]);
		e[v-'A'+1][u-'A'+1]=max(e[v-'A'+1][u-'A'+1],w);siz[v-'A'+1]=max(e[v-'A'+1][u-'A'+1],siz[v-'A'+1]);
	}
	char a,b;
	cin>>a>>b;
	int qd,zd;
	qd=a-'A'+1;zd=b-'A'+1;
	dijkstra(qd,zd);
	cout<<dis[zd];
}