#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

/**CU CAUTARE BINARA**/

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

const int MAXN = 55;
const int INF = 0x3f3f3f3f;
bool base[MAXN];//care baze sunt prietene
bool in_queue[MAXN];
int N, K, M, lanterna;
int best[MAXN][1005];//best[i][j] = distanta minima pentru ajunge in nodul i cu j wati ramasi

struct muchie {
    int to, timp, watt;
}aux;

vector<muchie> G[MAXN];
queue<int> Q;

void read() {
    fin >> N >> K;
    for (int i = 1; i <= N; ++i)
        fin >> base[i];
    fin >> M;
    int a, b, t, w;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b >> t >> w;
        aux.to = b; aux.timp = t; aux.watt = w;
        G[a].push_back(aux);
        aux.to = a;
        G[b].push_back(aux);
    }
}

void init() {
    memset(best, 0x3f, sizeof(best));
    memset(best[1], 0, sizeof(best[1]));
    memset(in_queue, 0, sizeof(in_queue));
    Q.push(1);
}

void BMF() {
    do {
        int node = Q.front();
        Q.pop();
        in_queue[node] = false;
        vector<muchie>::iterator it;
        for (it = G[node].begin(); it != G[node].end(); ++it) {
            for (int w = it->watt; w <= lanterna; ++w) {
                if (best[it->to][w - it->watt] > best[node][w] + it->timp) {
                    best[it->to][w - it->watt] = best[node][w] + it->timp;
                    if (base[it->to])
                        best[it->to][lanterna] = min(best[it->to][lanterna], best[it->to][w - it->watt]);
                    if (!in_queue[it->to]) {
                        Q.push(it->to);
                        in_queue[it->to] = true;
                    }
                }
            }
        }
    }while (!Q.empty());
}

int main() {
    read();
    int dmin = INF, lmin = 666013;
    int Left = 1, Right = 2 * K;
    while (Left <= Right) {
        lanterna = (Right - Left) / 2 + Left;
        init();
        BMF();
        int daux = INF;
        for (int i = 0; i <= lanterna; ++i)
            if (daux > best[N][i])
                daux = best[N][i];
        //nu s-a putut ajunge cu ajutorul acestei lanterne,
        //deci trebuie sa marim numarul de watti
//        cerr << Left << ' '  << lanterna << ' ' << Right << '\n';
//        cerr << dmin << ' ' << daux << ' ' << lmin << "\n\n\n";
        if (daux == INF || dmin < daux)
            Left = lanterna + 1;
        else {
            if (dmin >= daux) {
                dmin = daux;
                lmin = lanterna;
            }
            Right = lanterna - 1;
        }
    }
    fout << dmin << ' ' << lmin << '\n';
    fin.close();
    fout.close();
    return 0;
}