#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <climits>
#include <unordered_map>
#include <queue>


using namespace std;

vector <int> sol;

struct Road {
	int y, c, w;
	Road(int y, int c, int w): y(y), c(c), w(w) {}
};

int trav (unordered_map <int, vector <Road>> &g, vector <int> &fr, int n, int k) {
	
	vector <vector <int>> dst (n, vector <int>(k+1, INT_MAX)); //(dist, av watts)
	
	for (int i = 0; i <= k; i++)
		dst[0][i] = 0;
	
	
	queue <int> q;
	q.push(0);
	while (!q.empty()) {
		int x = q.front();
		q.pop();
		
		for(auto r: g[x]) {
			int y = r.y;
			bool yq = false;
			
			for (int i = 0; i <= k; i++) {
				if (dst[x][i] == INT_MAX)
					continue;
			
				int d = dst[x][i] + r.c;
				int w = i - r.w;
				//cout<<x<<" "<<y<<" "<<w<<endl;
				if (w < 0)
					continue;
				
				if (fr[y])
					w = k;
				
				int &dy = dst[y][w];
				
				if (dy > d) {
					dy = d;
					yq = true;
				}
			}
			
			if (yq)
				q.push(y);
		}
	}
	
	int sol = INT_MAX;
	for (int i = 0; i <= k; i++)
		sol = min(sol, dst[n-1][i]);
	
	return sol;
	
}


int main() {
    int n, k, m, x ,y, c, w;
    
    
    ifstream myfile;
    myfile.open ("lanterna.in");
    myfile>>n>>k;
    vector <int> fr(n);
    for (int i = 0; i < n; i++)
    	myfile>>fr[i];
    myfile>>m;
    unordered_map <int, vector <Road>> g;
    for (int i = 0; i < m; i++) {
    	myfile>>x>>y>>c>>w;
    	g[x-1].push_back(Road(y-1, c, w));
    	g[y-1].push_back(Road(x-1, c, w));
    }
    
    int mint = trav(g, fr, n, k);
    
    int lo = 1, hi = k;
   
    while (lo < hi) {
    	int lan = lo + (hi - lo)/2;
    	
    	int dst = trav(g, fr, n, lan);
    	
    	if (dst < 0 || dst > mint)
    		lo = lan + 1;
    	else
    		hi = lan;
    }
    
  
  
   //for (int i = 1; i <= k; i++)
   	//cout<<trav(g, fr, n, i)<<endl;
   	
   
   //cout<<mint<<endl;




    ofstream f2;
    f2.open ("lanterna.out");
     
    f2<<mint<<" "<<lo<<endl;
    f2.close();
  
      
    return 0;
}