#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <queue>
#define inf 0x3f3f3f3f
#define M 621
#define N 30201 
using namespace std;
struct no{
	int end;
	int next;
	int cost;
}path[N];
int e,head[N];
inline void Init(){
	e=0;
	memset(head,-1,sizeof(head));
}
inline void add(int u,int v,int w){
	path[e].end=v;
	path[e].cost=w;
	path[e].next=head[u];
	head[u]=e++;
}
int leader[N];
int dis[M][200],vis[M][200];
void spfa(int n){
    memset(vis,0,sizeof(vis));
	memset(dis,inf ,sizeof(dis));
	dis[1][0]=0;
	vis[1][0]=1;
	queue<pair<int ,int>  > Q;
	Q.push(make_pair(1,0));
	int u,v,w,l1,time,l2;
	while(!Q.empty()){
		u=Q.front().first;
		time=Q.front().second;
		l1=leader[u];
		Q.pop();
		vis[u][time]=0;
		for(int i=head[u];i!=-1;i=path[i].next){
			v=path[i].end,w=path[i].cost,l2=leader[v];
			if(l1==l2){
				if(dis[v][time]>w+dis[u][time]){
					dis[v][time]=w+dis[u][time];
					if(!vis[v][time]){
						vis[v][time]=1;
						Q.push(make_pair(v,time));
			
					}
				}
			}else {
			
			   	if(time+1<2&&dis[v][time+1]>w+dis[u][time]){
					dis[v][time+1]=w+dis[u][time];
					if(!vis[v][time+1]){
						vis[v][time+1]=1;
						Q.push(make_pair(v,time+1));
					}
				}
			}
		}
	}
}
int main(){
	int n,m;
	while(scanf("%d",&n),n){
		scanf("%d",&m);
		Init();
		int s,d,f;
		for(int i=0;i<m;i++){
			scanf("%d%d%d",&s,&d,&f);
			add(s,d,f);
			add(d,s,f);
		}
		int h;
		for(int i=0;i<n;i++){
			scanf("%d",&h);
			leader[i+1]=h;
		}
		spfa(n);
		if(dis[2][0]==inf&&dis[2][1]==inf)  printf("-1\n");
		else {
           printf("%d\n",dis[2][1]>dis[2][0]?dis[2][0]:dis[2][1]);
				
		}
		
	}
}