#include <iostream>
#include <queue>
#include <fstream>
#include <vector>
#include <cstring>
//#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
const int INF = 1e8;
const int di[] = {-1, 1, 0, 0};
const int dj[] = {0, 0, -1, 1};
struct node {
    int b, T, E;
    node () {}
    node(int _b, int _T, int _E) {
        b = _b;
        T = _T;
        E = _E;
    }
    
};
vector<node> graph[maxn];
int n, m;
int dp[maxn][2002];
int rec(int at, int money_left) {
    if(at == n) {
        return 0;
    }
    if(money_left == 0) {
        return INF;
    }
    if(dp[at][money_left] != -1) {
        return dp[at][money_left];
    }
    int res = INF;
    for(int i = 0; i < (int) graph[at].size(); i++) {
        int neighbour = graph[at][i].b;
        int time = graph[at][i].T;
        int money = graph[at][i].E;
        
        if(money_left >= money) {
            res = min(res, rec(neighbour, money_left - money) + time);
        }
    }
    return dp[at][money_left] = res;
}
int main() {
    ios_base::sync_with_stdio(false);
//    ifstream cin("in.txt");
    int S;
    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(node(b, c, d));
        graph[b].push_back(node(a, c, d));
    }
    memset(dp, -1, sizeof dp);
    int res = INF;
    for(int i = 1; i <= S; i++) {
        res = min(res, rec(1, i));
    }
    if(res >= INF) {
        res = -1;
    }
    cout << res << endl;
    
    return 0;
}