#include <bits/stdc++.h>
#define readFast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define nl cout << '\n'
#define afis(v) for (auto x : v) {cout << x << " ";} cout << '\n';
#define afisPii(v) for (auto x : v) {cout << x.first << " " << x.second << '\n';} cout << '\n';
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 100;

struct camp {
    int b, t, w;
};

int n, m, k;
vector<camp> graf[N];
bool friends[N];
int from[N], tMin = INT_MAX, wUsedMin = INT_MAX;

struct cont{
    int b, t, w, wMax;
};
struct cmp {
    bool operator()(cont x, cont y) {
        return x.t > y.t;
    }
};
priority_queue<cont, vector<cont>, cmp> coada;
int wMax[N], t[N];

void bfs() {
    coada.push({1, 0, 0});
    wMax[1] = 0;
    t[1] = 0;

    while(!coada.empty()) {
        int nod = coada.top().b;
        int timp = coada.top().t;
        int wUsed = coada.top().w;
        int wUsedMax = coada.top().wMax;
        coada.pop();
        //cout <<nod << " " << timp << " " << wUsed << " " << wUsedMax << '\n';
        if(nod == n) {
            if(timp < tMin) {
                tMin = timp;
                wUsedMin = wUsedMax;
            }
            if(timp == tMin)
                wUsedMin = min(wUsedMax, wUsedMin);
            continue;
        }

        for (int i = 0; i < sz(graf[nod]); ++i) {
            int to = graf[nod][i].b, tDrum = graf[nod][i].t, w = graf[nod][i].w;

            if(friends[nod]) {
                if(w <= k) {
                    if (timp + tDrum < t[to]) {
                        coada.push({to, timp + tDrum, w, max(wUsedMax, w)});
                        t[to] = min(t[to], timp + tDrum);
                    }
                    else {
                        coada.push({to, timp + tDrum, w, max(wUsedMax, w)});
                    }
                }
            }
            else {
                if(wUsed + w <= k) {
                    if(timp + tDrum < t[to]) {
                        coada.push({to, timp + tDrum, wUsed + w, max(wUsedMax, wUsed + w)});
                        t[to] = min(t[to], timp + tDrum);
                    }
                    else {
                        coada.push({to, timp + tDrum, wUsed + w, max(wUsedMax, wUsed + w)});
                    }
                }
            }
        }
    }
}

int main() {
    //ifstream fin("date.in.txt");
    ifstream fin("lanterna.in");
    ofstream fout("lanterna.out");
    fin >> n >> k;
    for (int i = 1; i <= n; ++i)
        fin >> friends[i];
    fin >> m;
    for (int i = 1; i <= m; ++i) {
        int a, b, t, w;
        fin >> a >> b >> t >> w;

        if(w > k)
            continue;

        graf[a].push_back({b, t, w});
        graf[b].push_back({a, t, w});
    }


    for (int i = 0; i < N; ++i)
        wMax[i] = t[i] = INT_MAX;
    bfs();

    assert(tMin != INT_MAX);
    assert(wUsedMin <= k);
    assert(wUsedMin != 0);
    fout << tMin << " " << wUsedMin << '\n';
    return 0;
}