#include 
#include 
#include 
#include 
#include 
using namespace std;

struct node
{
    int idx;
    int time;
    int cost;

    node(){}
    node(int _idx, int _time, int _cost)
    {
        idx=_idx;
        time=_time;
        cost=_cost;
    }
    bool operator<(const node &tmp) const
    {
        return time>tmp.time;
    }
};
int d[3005][2005];

int main()
{
//    ifstream cin("in.txt");
    int s,a,n;
    cin>>s>>a>>n;
    int x,y,t,m;
    vector>par[a+5];
    for(int i=0;i>x>>y>>t>>m;
        par[x].push_back({y,t,m});
        par[y].push_back({x,t,m});
    }
    priority_queueQ;
    Q.push(node(1,0,0));
    for(int i=0;i<=a;i++)
    {
        for(int j=0;j<=s;j++)
        {
            d[i][j]=2e9;
        }
    }
    d[1][0] = 0;
    while(!Q.empty())
    {
        node teme=Q.top();
        Q.pop();
        for(int i=0;i