#include <iostream>
#include <queue>
using namespace std;

int sourse, dest, road_length, toll;
int coin_limit, city_number, road_number;

int g[101][101] = {0};
int coin[101][101] = {0};
int l[101];

struct Node
{
    int location, length, money;
    friend bool operator < ( Node a, Node b)
    {
        return a.length > b.length;
    }
};

int bfs()
{
    priority_queue<Node> q;
    Node node, new_node;
    node.length = 0;
    node.location = 1;
    node.money = 0;
    q.push(node);

    for (int i = 1; i <= city_number; i++)
    {
        l[i] = INT_MAX;
    }

    while (!q.empty())
    {
        node = q.top();
        q.pop();
        int s = node.location;

        if (s == city_number)
        {
            return node.length;
        }

        if (node.money < l[s]) // 如果费用小于以前的值做
        {
            l[s] = node.money;
            for (int i = 1; i <= city_number; ++i)
            {
                if (g[s][i] > 0 && node.money + coin[s][i] <= coin_limit)
                {
                    new_node.location = i;
                    new_node.money = node.money + coin[s][i];
                    new_node.length = node.length + g[s][i];
                    q.push(new_node);
                }
            }
        }
    }
    return INT_MAX;
}

int main()
{
	int i;
	cin >> coin_limit >> city_number >> road_number;
	for (i = 0; i < road_number; ++i)
	{
	    cin >> sourse >> dest >> road_length >> toll;
	    g[sourse][dest] = road_length;
	    coin[sourse][dest] = toll;
	}

	int result = bfs();

	if (result == INT_MAX)
	    cout << "-1" << endl;
	else
        cout << result << endl;

	return 0;
}