/*
分析:
哎,很早以前就见到这个题了,当时觉得挺有难度的,
没啥思路就一直没做。今儿再一看,哎~~~,原来当时读错
题了。。。。。。
最短路+0-1DP,能量、最短路,两者哪个当背包都行。
2012-07-27
*/
#include"stdio.h" #include"string.h" int n; int map[111][111]; struct A { int val; int price; }E[111]; int MIN(int a,int b) { return a>b?b:a; } int MAX(int a,int b) { return a>b?a:b; } void floyd() { int k,i,l; for(k=0;k<=n;k++) for(i=0;i<=n;i++) for(l=0;l<=n;l++) map[i][l]=MIN(map[i][l],map[i][k]+map[k][l]); } int main() { int T; int m; int i,l; int a,b,c; int aim,total; int dp[100111]; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); for(i=0;i<=n;i++) { for(l=0;l<=n;l++) map[i][l]=11111111; map[i][i]=0; } while(m--) { scanf("%d%d%d",&a,&b,&c); map[a][b]=map[b][a]=MIN(map[a][b],c); } floyd(); aim=0; total=0; for(i=1;i<=n;i++) { scanf("%d",&E[i].val); aim+=E[i].val; E[i].price=map[0][i]; if(E[i].price!=11111111) total+=E[i].price; } memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { if(E[i].price==11111111) continue; for(l=total;l>=E[i].price;l--) { dp[l]=MAX(dp[l],dp[l-E[i].price]+E[i].val); } } aim=aim/2+1; for(i=0;i<=total;i++) if(dp[i]>=aim) break; if(i>total) printf("impossible\n"); else printf("%d\n",i); } return 0; }