#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
using namespace std;
int N;

int MIN = 99999999;

int last[108];

struct point 
{
	int mon;
	int length;

	bool vis ;
	
	int next;

}array[108][108];

void dfs(int start,int leftm,int len)
{
	if(leftm < 0)
		return ;
	if(start == N )
	{
		if(len < MIN)
			MIN = len;
		return;
	}
    if(len >= MIN)
		return;

	int i = 0;

	while((array[start][i].next) != -1)
	{	
		if(!(array[start][i].vis))
		{
			if(leftm-(array[start][i].mon) >= 0)
			{
				array[start][i].vis  = true;
				dfs(array[start][i].next ,leftm-(array[start][i].mon) ,len+(array[start][i].length));
				array[start][i].vis  = false;
			}
		}
		i ++;
	}
	return;
}
int main()
{
	int n,K;
	scanf("%d %d %d",&K,&N,&n);
	int i,j;

	for(i=0 ;i<=N ;i++)
		for(j=0 ;j<=N ;j++)
		{
			array[i][j].vis = false;
			array[i][j].next = -1;
		}

	memset(last,0,sizeof(last));

	for(i=0 ;i<n ;i++)
	{
		int a,b,c,d;
		scanf("%d %d %d %d",&a,&b,&c,&d);
		if(array[a][last[a]].next != -1)
		{
			last[a] ++;
		}
		array[a][last[a]].length = c;
		array[a][last[a]].mon = d;
		array[a][last[a]].next = b;
	}

	dfs(1,K,0);

	if(MIN == 99999999)
		printf("-1\n");
	else
		printf("%d\n",MIN);

	return 0;
}