#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("lanterna.in");
ofstream fout("lanterna.out");

const int INF = 1e9;

struct Muchie {
    int v, t, w;
};

struct Node {
    int nod, timp, bat;
    bool operator < (const Node & other) const {
        return timp > other.timp;
    }
};

int n, k, m;
vector<int> f;
vector<vector<Muchie>> graf;
int dp[55][1005];
bool ok;
int rez;

void dijkstra(int pmax)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= k; j++)
        {
            dp[i][j] = INF;
        }
    }
    
    for(int j = 0; j <= k; j++)
    {
        dp[1][j] = 0;
    }
    
    priority_queue <Node> pq;
    pq.push({1, 0, pmax});
    
    while(!pq.empty())
    {
        Node curent = pq.top();
        pq.pop();
        
        int u = curent.nod;
        int t = curent.timp;
        int b = curent.bat;
        
        if(dp[u][b] < t) 
            continue;
        
        for(auto &m : graf[u])
        {
            int nt = dp[u][b] + m.t;
            int nb = b - m.w;
            
            if(nb < 0) 
                continue;
            if(f[m.v]) 
                nb = pmax;
            
            if(dp[m.v][nb] > nt)
            {
                dp[m.v][nb] = nt;
                pq.push({m.v, nt, nb});
            }
        }
    }
    int mxt = INF;
    for(int j = 0; j <= k; j++)
    {
        if(dp[n][j] != INF)
        {
            mxt = min(mxt, dp[n][j]);
        }
    }
    
    rez = mxt;
    if(rez != INF) ok = true;
}

int main()
{
    fin >> n >> k;
    f.resize(n+1);
    graf.resize(n+1);
    
    for(int i = 1; i <= n; i++)
        fin >> f[i];
    fin >> m;
    for(int i = 0; i < m; i++)
    {
        int x, y, cost, watt;
        fin >> x >> y >> cost >> watt;
        graf[x].push_back({y, cost, watt});
        graf[y].push_back({x, cost, watt});
    }
    int st = 1, dr = k, wans = k, tans = INF;
    ok = false;
    dijkstra(k);
    tans = rez;
    
    while(st <= dr)
    {
        ok = false;
        rez = INF;
        int mid = (st + dr) / 2;
        dijkstra(mid);
        if(ok && rez == tans)
        {
            wans = mid;
            dr = mid - 1;
        }
        else 
        {
            st = mid + 1;
        }
    }
    
    fout << tans << " " << wans;
    return 0;
}