// 分层图最短路 Dijkstra 算法 O(mk*log(nk))
#include<bits/stdc++.h>
using namespace std;

const int N=1005;
int h[N],idx,to[N<<1],ne[N<<1],w[N<<1];
void add(int x,int y,int z){
  to[++idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx;
}
struct node{
  long long d; int v,s; //花费，点，速度
  bool operator<(const node &b)const&{
    return d>b.d;
  }
};
int n,m,a[N];
long long d[N][N]; //d[i][j]表示到点i使用速度j的最小花费

void dijkstra(){
  memset(d,0x3f,sizeof d); d[1][a[1]]=0;
  priority_queue<node> q;
  q.push({0,1,a[1]});
  while(!q.empty()){
    auto [dd,u,s]=q.top();q.pop();
    if(dd!=d[u][s])continue;
    for(int i=h[u];i;i=ne[i]){
      int v=to[i];
      long long ww=1ll*s*w[i]; //花费
      if(d[v][s]>d[u][s]+ww){  //不换速度
        d[v][s]=d[u][s]+ww;
        q.push({d[v][s],v,s});
      }
      if(d[v][a[v]]>d[u][s]+ww){ //换速度
        d[v][a[v]]=d[u][s]+ww;
        q.push({d[v][a[v]],v,a[v]});
      }
    }
  }
}
int main(){
  int t; cin>>t;
  while(t--){
    cin>>n>>m;
    idx=0; memset(h,0,sizeof h);
    for(int i=1,u,v,w;i<=m;i++){
      cin>>u>>v>>w;
      add(u,v,w);add(v,u,w);
    }
    for(int i=1;i<=n;i++)cin>>a[i]; //速度
    dijkstra();
    long long ans=1e18;
    for(int i=1;i<=n;i++)ans=min(ans,d[n][a[i]]);
    cout<<ans<<"\n";
  }
}