using namespace std;

#include<iomanip>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<cassert>
#include<numeric>
#include<cstring>
#include<sstream>
#include<algorithm>
#include<deque>

const int INFI=(1LL<<30)-100;
const long long INFL=(1LL<<62);
const double eps=1e-10;
const long double pi=acos(-1.0);
const int MAXN=60;
const int MAXK=1010;

int n,m,k;
bool base[MAXN];
int dp[MAXN][MAXK];

vector<pair<int,pair<int,int> > > v[MAXN];

int bellman(int lanterna){
    dp[1][lanterna]=0;
    queue<pair<int,int> > q;
    q.push(make_pair(1,lanterna));

    while(!q.empty()){
        int i=q.front().first;
        int ltlf=q.front().second;
        q.pop();

        if(base[i]){
            dp[i][lanterna]=dp[i][ltlf];
            ltlf=lanterna;
        }

        for(unsigned j=0;j<v[i].size();j++){
            int u=v[i][j].first;
            int watt=v[i][j].second.second;
            int tm=v[i][j].second.first;
            if( ltlf-watt>=0 && dp[i][ltlf]+tm < dp[u][ltlf-watt]){
                dp[u][ltlf-watt]=dp[i][ltlf]+tm;
                q.push(make_pair(u,ltlf-watt));
            }
        }
    }

    return *min_element(dp[n],dp[n]+k+1);
}

int main(){
    freopen("lanterna.in","r",stdin);
    freopen("lanterna.out","w",stdout);
    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++){
        int aux;
        scanf("%d",&aux);
        base[i]=aux;
    }

    scanf("%d",&m);

    for(int i=1;i<=m;i++){
        int x,y,T,W;
        scanf("%d%d%d%d",&x,&y,&T,&W);
        v[x].push_back(make_pair(y,make_pair(T,W)));
        v[y].push_back(make_pair(x,make_pair(T,W)));
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<=k;j++){
            dp[i][j]=INFI;
        }
    }
    int mn=bellman(k);

    int lo=1,hi=k;

    while(lo<hi){
        int mid=(lo+hi)/2;

        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                dp[i][j]=INFI;
            }
        }

        int srtst=bellman(mid);

        if(srtst==mn){
            hi=mid;
        }else{
            lo=mid+1;
        }
    }

    printf("%d %d",mn,lo);

    return 0;
}