#include <iostream>
using namespace std;

int mo[31];
int k[31];
int s[31][31];
int a[31];
int m,n;
int z[31];
int nn,h,tn,th;
bool ooo[31][31];

void abc(int i)
{
	int p,q,t;
	for (p=1;p<=n;p++)
	{
		if (k[p]==0)
		{
			k[p]++;
			tn++;
			a[tn]=p;
			th+=mo[p];
			t=i-1;
			for (q=1;q<=s[p][0];q++)
			{
				if (k[s[p][q]]==0)
					t--;
				k[s[p][q]]++;
			}
			if (t==0)
			{
				if ((tn>nn||(tn==nn&&th>h))&&th<=m)
				{
					nn=tn;
					h=th;
					for (q=1;q<=nn;q++)
						z[q]=a[q];
				}
			}
			else abc(t);
			a[tn]=0;
			tn--;
			th-=mo[p];
			k[p]--;
			for (q=1;q<=s[p][0];q++)
				k[s[p][q]]--;
		}
	}
}

void start()
{
	freopen("fish.in","r",stdin);
	freopen("fish.out","w",stdout);
	scanf("%d%d",&m,&n);
	int i,j,t,p,q;
	for (i=1;i<=n;i++)
	{
		scanf("%d%d",&j,&t);
		mo[j]=t;
	}
	p=1;
	q=1;
	while (p!=0&&q!=0)
	{
		scanf("%d%d",&p,&q);
		if (p!=0&&q!=0)
		{
			ooo[p][q]=true;
			ooo[q][p]=true;
		}
	}
	for (p=1;p<=n;p++)
		for (q=1;q<=n;q++)
		{
			if (ooo[p][q]==true)
			{
				s[p][0]++;
				s[p][s[p][0]]=q;
			}
		}
	for (i=1;i<=n;i++)
		k[i]=0;
	tn=0;
	th=0;
	abc(7);
}

int main()
{
	start();
	printf("%d %d\n",nn,h);
	int i;
	for (i=1;i<=nn;i++)
		printf("%d\n",z[i]);
	return 0;
}