#include<cstdio>

#include<set>

#include<cmath>

#include<stack>

#include<cstring>

#include<string>

#include<sstream>

#include<iostream>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn = +;

const int INF = 0x3f3f3f3f;

int lowcost[maxn],cost[maxn][maxn];

int dp[],power[maxn];

bool vis[maxn];

int n,m;

void Dijkstra(int st){

    for(int i = ;i <= n;i++){

        lowcost[i] = cost[][i];

        vis[i] = false;

    }

    lowcost[st] = ;

    for(int i = ;i < n;i++){

        int k = -,MIN = INF;

        for(int j = ;j <= n;j++){

            if(!vis[j] && lowcost[j] < MIN){

                MIN = lowcost[j];

                k = j;

            }

        }

        if(k == -) break;

        vis[k] = true;

        for(int j = ;j <= n;j++){

            if(!vis[j] && lowcost[j] > lowcost[k] + cost[k][j]){

                lowcost[j] = lowcost[k] + cost[k][j];

            }

        }

    }

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        memset(cost,INF,sizeof(cost));

        scanf("%d%d",&n,&m);

        while(m--){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            cost[u][v] = cost[v][u] = min(cost[u][v],w);

        }

        for(int i = ;i <= n;i++)

            scanf("%d",&power[i]);

        int st = ;

        for(int i = ;i <= n;i++){

            st += power[i];

        }

        st = st /  + ;

        Dijkstra();

        int ALL = ;

        for(int i = ;i <= n;i++){

            if(lowcost[i] != INF)

                ALL += lowcost[i];

        }

        memset(dp,,sizeof(dp));

        for(int i = ;i <= n;i++){

            if(lowcost[i] == INF) continue;

            for(int j = ALL;j >= lowcost[i];j--){

                dp[j] = max(dp[j],dp[j - lowcost[i]] + power[i]);

            }

        }

        int Min = -;

        for(int i = ;i <= ALL;i++){

            if(dp[i] >= st){

                Min = i;

                break;

            }

        }

        if(Min != -) printf("%d\n",Min);

        else printf("impossible\n");

    }

    return ;

}