1 /*
  2 Author:    Leo.W
  3 Descriptipn:  最短路問(wèn)題+01背包，好題啊。
  4 How to Do:  將路程即耗油量視作背包容積，取得的電量視作價(jià)值，那么就是給定價(jià)值，求滿足這一價(jià)值的最小容積。
  5             先求出自base點(diǎn)到其他各點(diǎn)的最短距離，再以此為基礎(chǔ)做0-1背包。
  6   */
  7 
  8 #include <cstdio>
  9 #include <string.h>
 10 #define MAXSIZE 101
 11 #define IMAX 10050
 12 char ch;
 13 int n,m;
 14 int dis[MAXSIZE][MAXSIZE];
 15 int cost[MAXSIZE];
 16 int value[MAXSIZE];
 17 int visited[MAXSIZE];
 18 int dp[IMAX];
 19 
 20 void dijiastra(){
 21     int i,j,pos;
 22     memset(visited,1,sizeof(visited));
 23     for(i=1;i<=n;i++)
 24         cost[i]=dis[0][i];
 25     for(i=1;i<=n;i++){
 26         int MIN=IMAX;
 27         for(j=1;j<=n;j++)
 28             if(visited[j]&&cost[j]<MIN){
 29                 MIN=cost[j];
 30                 pos=j;
 31             }
 32         if(MIN==IMAX)    break;
 33         visited[pos]=0;
 34         for(j=1;j<=n;j++){
 35             if(visited[j]&&cost[j]>cost[pos]+dis[pos][j])
 36                 cost[j]=cost[pos]+dis[pos][j];
 37         }
 38     }
 39 }
 40 inline void scan(int &x){
 41     while(ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
 42     while(ch=getchar(),ch>='0'&&ch<='9')x=10*x+ch-'0';
 43 }
 44 inline void init(){
 45     for(int i=0;i<=n;i++){
 46         for(int j=0;j<=n;j++)
 47             if(i==j)
 48                 dis[i][j]=0;
 49             else
 50                 dis[i][j]=IMAX;
 51     }
 52     memset(dp,0,sizeof(dp));
 53 }
 54 int main(){
 55     #ifdef ONLINE_JUDGE
 56     #else
 57         freopen("in.txt","r",stdin);
 58     #endif
 59     int t;
 60     scan(t);
 61     while (t--){
 62         scan(n);
 63         scan(m);
 64         init();
 65         int i,j;
 66         for(i=0;i<m;i++){
 67             int a,b,c;
 68             scan(a);
 69             scan(b);
 70             scan(c);
 71             if(dis[a][b]>c)
 72                 dis[a][b]=dis[b][a]=c;
 73         }
 74         for(i=1;i<=n;i++)
 75             scan(value[i]);
 76         dijiastra();
 77         int v=0,c=0,flag=0;
 78         for(i=1;i<=n;i++){
 79             v+=value[i];
 80             c+=cost[i];
 81             if(cost[i]==IMAX){
 82                 flag=1;
 83                 break;
 84             }        
 85         }
 86         if(flag){
 87             puts("impossible");
 88             continue;
 89         }
 90         for(i=1;i<=n;i++)
 91             for(j=c;j>=cost[i];j--){
 92                 if(dp[j-cost[i]]+value[i]>dp[j])
 93                     dp[j]=dp[j-cost[i]]+value[i];
 94             }
 95         int target=v/2;
 96         for(j=1;j<=c;j++)
 97             if(dp[j]>target)
 98                 break;
 99         printf("%d\n",j);
100     }
101     return 0;
102 }
103