#include <bits/stdc++.h>
#define NMAX 1010
#define MOD 1e9
using namespace std;
ifstream fin("lanterna.in");
ofstream fout("lanterna.out");
struct poz{
    int nod,t, w;//nod, dist, watt

};
struct poz2{
    int nod,  w;

};

queue<poz2>q;
vector<poz> v[NMAX];
int n, k, djk[NMAX][NMAX], x, y, p[NMAX],use[NMAX][NMAX];

int dijkstra(int watt)
{
    for(int i=1;i<=n;++i)
        for(int j=0;j<=watt;++j)
        {
            djk[i][j]=MOD; //[nod, watt]=dist
            use[i][j]=0;
        }
    djk[1][watt]=0;

    int j=0;
    q.push({1,watt});//nod, dist(t), watt
    while(q.empty()==false)
    {
        x=q.front().nod;
        y=q.front().w;
        q.pop();
        for(auto i:v[x])
        {
            if(p[i.nod]==1)
                j=watt;
            else j=y-i.w;

            if(y-i.w>=0)
                if(djk[x][y]+i.t<djk[i.nod][j])
                {
                    djk[i.nod][j]=djk[x][y]+i.t;
                    q.push({i.nod, j});
                }
        }
    }

    int dmin=MOD;
    for(int i=0;i<=watt;++i)
        dmin=min(dmin, djk[n][i]);
    return dmin;
}

int m,a, b, st, dr, mij, d, answ, ansd;
int main()
{
    fin>>n>>k;
    for(int i=1;i<=n;++i)
        fin>>p[i];
    fin>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y>>a>>b;
        v[x].push_back({y,a,b});//dist, watt
        v[y].push_back({x,a,b});
    }

    st=1;
    dr=k;
    answ=k;
    ansd=dijkstra(k);
    while(st<=dr)
    {
        mij=(st+dr)/2;
        d=dijkstra(mij);
        if(d==ansd)
        {
            answ=mij;
            ansd=d;
            dr=mij-1;
        }
        else st=mij+1;
    }

    fout<<ansd<<" "<<answ;
    return 0;
}