#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define maxn 100000

 using namespace std;

 const int inf=<<;

 int n,m,st,ed,c;

 int dis[maxn];

 bool vis[maxn];

 int g[][];

 int val[maxn];

 int dp[maxn];

 void dijkstra()

 {

     memset(vis,false,sizeof(vis));

     for(int i=; i<=n; i++) dis[i]=(i==?:inf);

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

     {

         int m=inf,x;

         for(int y=; y<=n; y++) if(!vis[y]&&dis[y]<m) m=dis[x=y];

         vis[x]=true;

         for(int y=; y<=n; y++) dis[y]=min(dis[y],dis[x]+g[x][y]);

     }

 }

 int main()

 {

     int t;

     scanf("%d",&t);

     while(t--)

     {

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

         memset(val,,sizeof(val));

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

         {

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

             {

                 if(i==j) g[i][j]=;

                 else g[i][j]=inf;

             }

         }

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

         {

             scanf("%d%d%d",&st,&ed,&c);

             g[st][ed]=g[ed][st]=min(g[st][ed],c);

         }

         int ans=;

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

         {

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

             ans+=val[i];

         }

         dijkstra();

         int mm=ans;

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

         {

             dp[i]=inf;

         }

         dp[]=;

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

         {

             if(dis[i]!=inf)

             {

                 for(int v=mm; v>=val[i]; v--)

                 {

                     dp[v]=min(dp[v],dp[v-val[i]]+dis[i]);

                 }

             }

         }

         mm=mm/+;

         int m1=inf;

         for(int i=mm; i<=ans; i++)

         {

             m1=min(m1,dp[i]);

         }

         if(m1>=inf) printf("impossible\n");

         else printf("%d\n",m1);

     }

     return ;

 }