#include <fstream>
#include <vector>
#include <array>
#include <queue>
#include <limits>
using namespace std;

std::ifstream in("lanterna.in");
std::ofstream out("lanterna.out");

const int nmax = 55;
const int wmax = 1005;
using pii = pair<int, int>;

struct node_t {
    int v;
    int c, w;
    node_t(int v, int c, int w) :
        v(v), c(c), w(w) {}
};

array<int, nmax> is_friend;
vector<node_t> graph[nmax];
array<int, wmax> best[nmax];
array<bool, wmax> done[nmax];

int dijkstra(int W, int start, int finish) {
    priority_queue<pii, vector<pii>, greater<pii>> heap;
    for (int i = 2; i < nmax; ++i) {
        fill(best[i].begin(), best[i].end(), numeric_limits<int>::max());
        fill(done[i].begin(), done[i].end(), false);
    }
    heap.push({start, W});
    for (int i = 0; i <= W; ++i)
        best[start][i] = 0;

    while (!heap.empty()) {
        int u = heap.top().first;
        int w = heap.top().second;

        heap.pop();
        // if (done[u][w]) continue;
        // done[u][w] = true;
        for (auto& n : graph[u])
            if (n.w <= w) {
                int new_w = (is_friend[n.v]) ? W : w - n.w;
                if (best[n.v][new_w] > best[u][w] + n.c) {
                    best[n.v][new_w] = best[u][w] + n.c;
                    heap.push({n.v, new_w});
                }
            }
    }

    int ret = numeric_limits<int>::max();
    for (int i = 0; i <= W; ++i) {
        ret = min(ret, best[finish][i]);
    }
    return ret;
}

int main() {
    int n, m, k;
    in >> n >> k;

    for (int i = 1; i <= n; ++i)
        in >> is_friend[i];
    in >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v, c, w;
        in >> u >> v >> c >> w;
        graph[u].push_back(node_t(v, c, w));
        graph[v].push_back(node_t(u, c, w));
    }

    int result_d = dijkstra(k, 1, n);
    int pos = 0;
    int step = 1 << 11;
    while (step >>= 1)
        if (pos + step <= k && (dijkstra(pos + step, 1, n) != result_d))
            pos += step;
    out << result_d << ' ' << pos + 1 << '\n';

    return 0;
}