#include <cstdio>
#include <climits>

#define I_F "snipers.in"
#define O_F "snipers.out"

const short MAXn=50+1;
const short MAXc=100;
const short S=0;

struct que
{
	short x;
	que *next;
};
struct edge
{
	short x,c;
	edge *op, *next;
}*map[MAXn];
short n,T;
short d[MAXn];

void Input();
void Spfa();
inline int Min(const int&, const int&);
int Sap(const short&, const int&);
void Output();

int main()
{
	int m;
	freopen(I_F,"r",stdin);
	freopen(O_F,"w",stdout);
	for (scanf("%d",&m); m>0; --m)
	{
		Input();
		Spfa();
		Output();
	}
	return 0;
}

void Input()
{
	unsigned short m;
	short a[MAXn],x,y;
	edge *temp;
	scanf("%hd%hd",&n,&m);
	T=n;
	for (short i=0; i<=n; map[i++]=NULL);
	a[S]=0;
	a[T]=SHRT_MAX-MAXc;
	for (short i=1; i<n; scanf("%hd",&a[i++]));
	for (unsigned short i=0; i<m; ++i)
	{
		scanf("%hd%hd",&x,&y);
		temp=map[x];
		map[x]=new edge;
		map[x]->x=y;
		map[x]->c=a[y];
		map[x]->next=temp;
		temp=map[y];
		map[y]=new edge;
		map[y]->x=x;
		map[y]->c=a[x];
		map[y]->next=temp;
		map[x]->op=map[y];
		map[y]->op=map[x];
	}
}

void Spfa()
{
	for (short i=0; i<n; d[i++]=SHRT_MAX-1);
	que *p[MAXn]={NULL};
	que *head, *tail, *temp;
	head=new que;
	head->x=n;
	head->next=0;
	tail=p[n]=head;
	
	while (head!=NULL)
	{
		for (edge *e=map[head->x]; e!=NULL; e=e->next)
			if (d[head->x]+1<d[e->x])
			{
				d[e->x]=d[head->x]+1;
				if (p[e->x]==NULL)
				{
					temp=new que;
					temp->x=e->x;
					p[e->x]=temp;
					if (head->next!=NULL && p[e->x]<p[head->next->x])
					{
						temp->next=head->next;
						head->next=temp;
					}
					else
					{
						temp->next=NULL;
						tail->next=temp;
						tail=temp;
					}
				}
			}
		temp=head;
		head=head->next;
		delete temp;
	}
}

inline int Min(const int &a, const int &b)
{
	return (a<b)?a:b;
}

int Sap(const short &u, const int &flow)
{
	if (u==T)
		return flow;
	int now=0, t;
	short v;
	for (edge *e=map[u]; e!=NULL; e=e->next)
	{
		v=e->x;
		if (e->c>0 && d[v]==d[u]-1)
		{
			t=Sap(v,Min(flow-now,e->c));
			if (t>0)
			{
				e->c-=t;
				e->op->c+=t;
				now+=t;
				if (now==flow)
					return now;
			}
		}
	}
	++d[u];
	return now;
}

void Output()
{
	int ans=0;
	do
	{
		ans+=Sap(0,INT_MAX);
	} while (d[S]<=n);
	printf("%d\n",ans);
}