1 #include <cstdio>
  2 #include <cstring>
  3 #include <queue>
  4 #define MAX 100005
  5 #define LL int
  6 #define MAXN 105
  7 #define INF 99999999
  8 #define max(x,y) (x>y ? x : y)
  9 #define min(x,y) (x<y ? x : y)
 10 #define DEBUG(x) printf("Line: %4\n",x)
 11 using namespace std;
 12 
 13 typedef struct{
 14     int to;
 15     int l;
 16     int next;
 17 }edge;
 18 
 19 int p[MAXN],tot;
 20 edge e[MAX];
 21 
 22 void add(int u,int v,int l){
 23     e[tot].to=v;
 24     e[tot].l=l;
 25     e[tot].next=p[u];
 26     p[u]=tot++;
 27 }
 28 
 29 
 30 int map[MAXN][MAXN];
 31 
 32 void reset(){
 33     memset(p,-1,sizeof(p));
 34     memset(e,0,sizeof(e));
 35     tot=0;
 36     //memset(map,-1,sizeof(map));        //邻接矩阵用
 37 }
 38 
 39 LL dis[MAXN];
 40 int n,m;
 41 
 42 
 43 bool vin[MAXN];
 44 
 45 void spfa(){
 46     queue<int> q;
 47     dis[0]=0;
 48     memset(vin,0,sizeof(vin));
 49     for(int i=1;i<=n;i++){
 50         dis[i]=INF;
 51     }
 52     q.push(0);
 53     vin[0]=1;
 54     while(!q.empty()){
 55         int u=q.front();
 56         vin[u]=0;
 57         q.pop();
 58         for(int v=p[u];v!=-1;v=e[v].next){
 59             //DEBUG(43);
 60             int l=dis[u]+e[v].l;
 61             if(dis[e[v].to]>l){
 62                 dis[e[v].to]=l;
 63                 if(!vin[e[v].to]){
 64                     q.push(e[v].to);
 65                     vin[e[v].to]=1;
 66                 }
 67             }
 68         }
 69         //DEBUG(52);
 70     }
 71 }
 72 
 73 //dij
 74 /*
 75 bool flag[MAXN];
 76 void dij(int r){
 77     int u;
 78     LL minn;
 79     memset(flag,0,sizeof(flag));
 80     for(int i=0;i<=n;i++){
 81         dis[i]=INF;
 82     }
 83     dis[r]=0;
 84     for(int i=0;i<=n;i++){
 85         u=-1;
 86         minn=INF;
 87         for(int j=0;j<=n;j++){
 88             if(!flag[j] && minn>dis[j]){
 89                 u=j;
 90                 minn=dis[j];
 91             }
 92         }
 93         if(u==-1) return ;
 94         flag[u]=1;
 95 
 96         //for(int v=p[u];v!=-1;v=e[v].next){
 97         //    dis[e[v].to]=min(dis[e[v].to],dis[u]+e[v].l);
 98         // }
 99 
100         for(int i=0;i<=n;i++){
101             if(map[u][i]!=-1){
102                 dis[i]=min(map[u][i]+dis[u],dis[i]);
103             }
104         }
105     }
106 }
107 */
108 int w[MAXN];
109 LL dp[MAX];
110 LL minn,wsum;
111 
112 int main()
113 {
114     int t;
115     int st,ed,l;
116     //freopen("data.txt","r",stdin);
117     scanf("%d",&t);
118     while(t--){
119         scanf("%d %d",&n,&m);
120         reset();
121         for(int i=0;i<m;i++){
122             scanf("%d %d %d",&st,&ed,&l);
123             add(st,ed,l);
124             add(ed,st,l);
125             /*
126             if(map[st][ed]==-1 || map[st][ed]>l){
127                 map[st][ed]=l;
128                 map[ed][st]=l;
129             }
130             */
131         }
132         wsum=0;
133         for(int i=1;i<=n;i++){
134             scanf("%d",&w[i]);
135             wsum+=w[i];
136         }
137         spfa();
138         //dij(0);
139         for(int i=0;i<=wsum;i++) dp[i]=INF;
140         dp[0]=0;
141         for(int i=1;i<=n;i++){
142                 for(int j=wsum;j>=w[i];j--){
143                     dp[j]=min(dp[j-w[i]]+dis[i],dp[j]);
144                     //printf("%d ",dp[j]);
145                 }
146                 //printf("\n");
147         }
148         minn=INF;
149         for(LL i=(wsum)/2+1;i<=wsum;i++){
150             minn=min(dp[i],minn);
151         }
152         if(minn!=INF) printf("%d\n",minn);
153         else printf("impossible\n");
154     }
155 
156     return 0;
157 }