思路：最短路求出到每个点的最小代价，然后01背包，求出某一代价所能拿到的最大价值，然后搜索最后结果。
代码：
#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 ;
}