#include 
#include 
#include 
using namespace std;
struct node{
int distance;
int cena;
int index;

node(){


}

node(int _index, int _distance, int _cena){
index=_index;
distance=_distance;
cena=_cena;
}

bool operator <(const node&tmp)const{
return distance > tmp.distance;
}





};
int main()
{
    int n;
    int m;
    int S;
    int S1=200000000;


    cin>>S;
    cin>>n>>m;
    int matrica[n+1][S + 1];
    vectorv[n+1];

    for(int x1=0; x1>indexa>>indexb>>distance>>cost;
    v[indexa].push_back(node(indexb, distance, cost));
    v[indexb].push_back(node(indexa, distance, cost));
    }
    priority_queuepq;
    pq.push(node(1, 0, 0));

    matrica[1][0]=0;

    while(!pq.empty()){
    node cnode=pq.top();
    pq.pop();
    for(int h=0; hdistance+cnode.distance)){
    matrica[sosed][cena+cnode.cena]=distance+cnode.distance;
    pq.push(node(sosed, distance+cnode.distance, cena+cnode.cena));
    }
    }


    }
     for(int y=0; y<=S; y++){
     if(matrica[n][y]