#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
struct node {
    int idx, shortest_time, money;

    node () {}
    node(int _idx, int _shortest_time, int _money) {
        idx = _idx;
        shortest_time = _shortest_time;
        money = _money;
    }

    bool operator < (const node & tmp) const {
        if(shortest_time == tmp.shortest_time) {
            return money > tmp.money;
        }
        return shortest_time > tmp.shortest_time;
    }

};

struct vertex {
    int b, time, money;
    vertex() {}
    vertex(int _b, int _time, int _money) {
        b = _b;
        time = _time;
        money = _money;
    }

};


vector<vertex> graph[3005];
bool visited[3005][2005];
int main() {
    memset(visited, false, sizeof visited);

    int S, n, m;
    cin >> S >> n >> m;

    for(int i = 0; i < m; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        graph[a].push_back(vertex(b, c, d));
        graph[b].push_back(vertex(a, c, d));
    }

    priority_queue<node> pq;
    pq.push(node(1, 0, 0));

    while(!pq.empty()) {
        node c = pq.top();
        pq.pop();

        if(c.idx == n) {
            cout << c.shortest_time << endl;
            return 0;
        }

        if(visited[c.idx][c.money]) continue;
        visited[c.idx][c.money] = true;

        for(int i = 0; i < (int) graph[c.idx].size(); i++) {
            int neighbour = graph[c.idx][i].b;
            int time = graph[c.idx][i].time;
            int money = graph[c.idx][i].money;

            if(c.money + money <= S and !visited[neighbour][c.money + money]) {
                pq.push(node(neighbour, c.shortest_time + time, c.money + money));
            }
        }
    }

    cout << -1 << endl;
    return 0;
}