#include<iostream>

#include<algorithm>

#include<string.h>

#include<queue>

#define inf 0x3f3f3f3f

#define maxn 308

using namespace std;

int K,N,M,cnt;

int head[maxn],ans;

bool vis[maxn][];

int dist[maxn][];

struct Edge

{

    int to;

    int val;

    int m;

    int next;

}edge[maxn*maxn];

struct Node

{

    int x;

    int k;

    int val;

    Node(){};

    Node(int _x,int _k,int _val){

        x=_x,k=_k,val=_val;

    }

    bool operator < (const Node a) const{

        return val>a.val;

    }

 };

inline void add(int u,int v,int val,int m)

{

    edge[++cnt].to=v;

    edge[cnt].val=val;

    edge[cnt].m=m;

    edge[cnt].next=head[u];

    head[u]=cnt;

    return;

}

void dijkstra()

{

    priority_queue<Node> q;

    while(!q.empty()) q.pop();

    for(int i=;i<=N;i++){

        for(int j=;j<=K;j++){

            dist[i][j]=inf;

        }

    }

    q.push(Node(,K,));

    dist[][K]=;

    while(!q.empty())

    {

        int u=q.top().x,k=q.top().k;

        q.pop(); // 这里可以直接 if( u == N) ans = q.top().val ，即为答案

        if(vis[u][k]) continue;

        vis[u][k]=true;

        for(int i=head[u];i;i=edge[i].next){

            int v=edge[i].to;

            if(k>=edge[i].m){

                if(dist[v][k-edge[i].m]>dist[u][k]+edge[i].val){

                    dist[v][k-edge[i].m]=dist[u][k]+edge[i].val;

                    q.push(Node(v,k-edge[i].m,dist[v][k-edge[i].m]));

                }

            }

        }

    }

    return;

}

int main()

{

    //freopen("test.in","r",stdin);

    //freopen("test.out","w",stdout);

    scanf("%d%d%d",&K,&N,&M);

    int A,B,C,D;

    while(M--)

    {

        scanf("%d%d%d%d",&A,&B,&C,&D);

        add(A,B,C,D);

    }

    ans=inf;

    dijkstra();

    for(int i=;i<=K;i++){

        ans=min(ans,dist[N][i]);

    }

    if(ans==inf) printf("-1\n");

    else printf("%d\n",ans );

}