#include <bits/stdc++.h>

using namespace std;

#define maxn 3000

#define INF 1e9

int dis[][],l,n,m,s,t;

struct {

    int a,b,c,flow;

}a[maxn*],tmp[maxn*];

bool fz1[],vis[];

int d[],head[];

void arr(int x,int y,int z)

{

    a[++l].a=head[x];

    a[l].b=y;

    a[l].c=z;

    a[l].flow=;

    head[x]=l;

}

queue<int> q;

bool bfs(){

    memset(vis,,sizeof(vis));

    queue<int> q;

    q.push(s);

    d[s]=; vis[s]=;

    while (!q.empty())

    {

        int x=q.front();q.pop();

        int u=head[x];

        while (u)

        {

            int v=a[u].b;

            if (!vis[v]&&a[u].c>a[u].flow)

            {

                vis[v]=;

                d[v]=d[x]+;

                q.push(v);

            }

            u=a[u].a;

        }

    }

    return(vis[t]);

}

int dfs(int x,int y)

{

    if (x==t||y==) return y;

    int flow=,f,tmp;

    int u=head[x];

    while (u)

    {

        int v=a[u].b;

        if (d[x]+==d[v]&&(f=dfs(v,min(y,a[u].c-a[u].flow)))>)

        {

            a[u].flow+=f;

            if (u%) tmp=u+; else tmp=u-;

            a[tmp].flow-=f;

            flow+=f;

            y-=f;

            if (y==) break;

        }

        u=a[u].a;

    }

    return(flow);

}

int maxflow()

{

    int flow=;

    while (bfs())

    {

        flow+=dfs(s,INF);

    }

    return(flow);

}

void get_ans(int ss,int tt)

{

    for (int i=;i<=l;i++) a[i].flow=;

    bool tmp3[],fz2[];

    s=ss; t=tt;

    int ans=maxflow();

    memcpy(tmp3,vis,sizeof(vis));

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

      if (vis[i])

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

          if (!vis[j])

            dis[i][j]=min(dis[i][j],ans),dis[j][i]=min(ans,dis[j][i]);

    int tmp1=,tmp2=,num=;

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

      if (vis[i]&&fz1[i])

      {

          num++;

          if (!tmp1) tmp1=i; else tmp2=i;

      }

    memcpy(fz2,fz1,sizeof(fz1));

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

      if (!vis[i]) fz1[i]=;

    if (num>=)

    {

    /*    l=0; memset(head,0,sizeof(head));

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

          if (vis[tmp[i].a]&&vis[tmp[i].b]&&

              fz1[tmp[i].a]&&fz1[tmp[i].b])

          {

               arr(tmp[i].a,tmp[i].b,tmp[i].c);

               arr(tmp[i].b,tmp[i].a,tmp[i].c);

          } */

         get_ans(tmp1,tmp2);

    }

    memcpy(vis,tmp3,sizeof(tmp3));

    memcpy(fz1,fz2,sizeof(fz2));

    tmp1=,tmp2=,num=;

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

      if (!vis[i]&&fz1[i])

      {

          num++;

          if (!tmp1) tmp1=i; else tmp2=i;

      }

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

      if (vis[i]) fz1[i]=;

    if (num>=)

    {

    /*    l=0; memset(head,0,sizeof(head));

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

          if (!vis[tmp[i].a]&&!vis[tmp[i].b]

          &&  fz1[tmp[i].a]&&fz1[tmp[i].b])

          {

               arr(tmp[i].a,tmp[i].b,tmp[i].c);

               arr(tmp[i].b,tmp[i].a,tmp[i].c);

          } */

        get_ans(tmp1,tmp2);

    }

    memcpy(fz1,fz2,sizeof(fz2));

}

int main()

{

    std::ios::sync_with_stdio(false);

    int T;

    cin>>T;

    for (int p=;p<=T;p++)

    {

        l=; memset(head,,sizeof(head));

        memset(fz1,,sizeof(fz1));

    cin>>n>>m;

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

      for (int j=;j<=n;j++) dis[i][j]=INF;

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

    {

        int c,d,e;

        cin>>c>>d>>e;

        tmp[i].a=c; tmp[i].b=d; tmp[i].c=e;

        arr(c,d,e); arr(d,c,e);

    }

    get_ans(,n);

    int q;

    cin>>q;

    int x;

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

    {

        cin>>x;

        int ans=;

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

          for (int j2=j1+;j2<=n;j2++)

            if (dis[j1][j2]<=x||dis[j1][j2]==INF) ans++;

        cout<<ans<<endl;

    }

    cout<<endl;

    }

    return ;

}