/**
 *    author:  orzvanh14 ( Độc cô cầu đặc )
 *    created: 18.04.2026 03:56:02
 *    too lazy to update time
**/
// i wants to take ioi
//binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
#include <bits/stdc++.h>

using namespace std;

#define int long long
#define nn "\n"
#define pi pair<int, int>
#define ti tuple<int, int, int>
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define pb push_back
#define TASK " "

#define ms(a, x) memset(a, x, sizeof(a))
#define all(a) a.begin(), a.end()
#define All(a, n) a + 1, a + 1 + n

#define LOG 19

const int INF = 1e18;
const int N = 1e3 + 5;
const int maxn = 100 + 5;
const int mod = 1e9 + 7;


struct node{
	int kc, u, st;
	bool operator<(const node& other) const {
        return kc > other.kc; 
    }
};
struct edge{
	int v, w, h;
};
int t, n, m;
int a[N];
// vector<int> d(N, INF);
void nhap(){
    cin >> t;

}
vector<pi> adj[N];
void dijkstra(int s){
	vector<vector<int>> d(N, vector<int>(N, INF));
	priority_queue<node> q;
    d[s][1] = 0;
    q.push({d[s][1], s, 1});
    while(!q.empty()){
        node Top = q.top(); q.pop();
        int kc = Top.kc;
        int u = Top.u;
        int st = Top.st;
        if(kc > d[u][st]) continue;
		for(auto [v, w] : adj[u]){
			// tiếp tục dùng loại xe trước đó
			if(d[v][st] > d[u][st] + w * a[st]){
				d[v][st] = d[u][st] + a[st] * w;
				q.push({d[v][st], v, st});
			}
			// mua xe mới
			if(d[v][v] > d[u][st] + w * a[st]){
				d[v][v] = d[u][st] + a[st] * w;
				q.push({d[v][v], v, v});
			}
			
		}

    }
    int ans = INF;
    for(int i = 1; i <= n; i++){
		ans = min(ans, d[n][i]);
	}		
	cout << ans << nn;	
}
void solve(){
	while(t--){
		cin >> n >> m;
		for(int i = 1; i <= m; i++){
			int x, y, w;
			cin >> x >> y >> w;
			adj[x].eb(y, w);
			adj[y].eb(x, w);
		}
		for(int i = 1; i <= n; i++){
			cin >> a[i];
		}
		dijkstra(1);
		for(int i = 1; i <= n; i++) adj[i].clear();
	}
}
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	nhap();
	solve();
	return 0;
}