#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
#define on pair <int, int>
#define onn pair <int, on>
using namespace std;
ifstream fin("lanterna.in");
ofstream fout("lanterna.out");

int n, k, m, h1=INF, h2;
int coada[55][1005], tip[55], Tmin[55][1005];
queue <on> q;
vector <onn> v[55];

void citire()
{
    fin >> n >> k;
    for (int i = 1; i <= n; i++)
        fin >> tip[i];
    fin >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, T, W;
        fin >> a >> b >> T >> W;
        v[a].push_back({b, {T, W}});
        v[b].push_back({a, {T, W}});
    }
}
int bellman(int so)
{
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= so; j++)
            Tmin[i][j] = INF;
    Tmin[1][so] = 0;
    q.push({1, so});
    coada[1][so] = 1;
    int mn = INF;
    while (!q.empty())
    {
        int nod = q.front().first;
        int put = q.front().second;
        q.pop();
        coada[nod][put] = 0;
        if (nod == n)
            mn = min(mn, Tmin[nod][put]);
        vector <onn> :: iterator it;
        for (it = v[nod].begin(); it != v[nod].end(); it++)
        {
            onn nr=*it;
            int lol = put-nr.second.second;
            int next = nr.first;
            int timp = nr.second.first;
            if (lol >= 0)
            {
                if (tip[next] == 1)lol = so;
                if (Tmin[next][lol] > Tmin[nod][put] + timp)
                {
                    Tmin[next][lol] = Tmin[nod][put] + timp;
                    if (coada[next][lol] == 0)
                    {
                        q.push({next, lol});
                        coada[next][lol] = 1;
                    }
                }
            }
        }
    }
    if (mn != INF)
        return mn;
    return 0;
}
void solve()
{
    int st = 1,dr = k - 1, act, mij;
    h1 = bellman(k);
    h2 = k;
    while(st <= dr)
    {
        mij = (st+dr)/2;
        act = bellman(mij);
        if(act == h1)
        {
            dr = mij-1;
            h2 = mij;
        }
        else st = mij+1;
    }
}
int main()
{
    citire();
    solve();
    fout << h1 << " " << h2 <<"\n";
    return 0;
}