#include <bits/stdc++.h>

using namespace std;
ifstream f ("lanterna.in");
ofstream g ("lanterna.out");
struct edge{
    int to , nt , nw;
    bool operator < (edge r) const{
        if (nt == r.nt)
            return nw < r.nw;
        return nt < r.nt;
    }
};
int base [51] , n , dp [51];
vector <edge> v [51];
priority_queue <edge , vector <edge> , less <edge> > pq;
bool viz [51];
int solve (int start , int cap , int tip){
    while (pq.size ())
        pq.pop ();
    fill (dp + 1 , dp + 1 + n , (1 << 30));
    pq.push ({start , 0 , 0});
    dp [start] = 0;
    viz [start] = true;
    while (pq.size ()){
        edge x = pq.top ();
        while (pq.size () && viz [pq.top ().to])
            pq.pop ();
        if (base [x.to])
            x.nw = 0;
        for(edge y : v [x.to]){
            if (dp [y.to] > dp [x.to] + y.nt){
                if (x.nw + y.nw <= cap){
                    if (y.to == n && tip)
                        return 1;
                    pq.push ({y.to , dp [x.to] , x.nw + y.nw});
                    dp [y.to] = dp [x.to] + y.nt;
                    viz [y.to] = true;
                }
            }
        }
    }
    if (tip)
        return 0;
    return dp [n];
}
int main (){
    int k;
    f >> n >> k;
    for(int i = 1 ; i <= n ; ++ i)
        f >> base [i];
    int m;
    f >> m;
    for(int i = 1 ; i <= m ; ++ i){
        int a , b , W , T;
        f >> a >> b >> T >> W;
        v [a].push_back ({b , T , W});
        v [b].push_back ({a , T , W});
    }
    int tmin = solve (1 , k , 0);
    int pas = (1 << 9) , r = 0;
    while (pas){
        if (pas + r <= k && ! solve (1 , pas + r , 1))
            r += pas;
        pas >>= 1;
    }
    g << tmin << ' ' << r + 1 << '\n';
    return 0;
}