#include <stdio.h>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;

#define nmax 50 

vector<int> G[nmax+10], CT[nmax+10], CW[nmax+10];
int  N, K, M, Tmin, obj_friend[nmax+10];
const int INF=2000000000;


void read()
	{freopen("lanterna.in","r",stdin);
	 int i,a,b,t,w; 
	 scanf("%d %d",&N,&K);
	 for(i=1;i<=N;i++)
		  scanf("%d",&obj_friend[i]);
	 scanf("%d",&M);
     for(i=1;i<=M;i++)
		              {
		   scanf("%d %d %d %d",&a,&b,&t,&w);
		   G[a].push_back(b);
		   CW[a].push_back(w);
		   CT[a].push_back(t);
		   G[b].push_back(a);
		   CW[b].push_back(w);
		   CT[b].push_back(t);
		  }
	 fclose(stdin);
	}
int t_bell_f(int W)
    {long long int dt[nmax+10], dw[nmax+10], nodcur, i;     
     bitset<nmax+10> in_queue(false); 
     queue<long long int> Q;
           
     for(i=2;i<=N;i++)  dt[i]=INF ; //init coada
     for(i=2;i<=N;i++)  dw[i]=INF ;	 
     dt[1]=0, dw[1]=0, Q.push(1), in_queue[1].flip();
	 
     while(!Q.empty())    
			   {nodcur=Q.front();
                Q.pop();
                in_queue[nodcur].flip();
                for(i=0;i<G[nodcur].size();i++)
						if(dw[nodcur]+CW[nodcur][i]<=W)  //poa sa mearga de la nodcur la G[nodcur][i]?
							{if(dt[nodcur]+CT[nodcur][i] < dt[ G[nodcur][i] ] )
							         {dt[ G[nodcur][i] ] = dt[nodcur]+CT[nodcur][i];
							 
									  if(!in_queue[ G[nodcur][i]] )
											  Q.push(G[nodcur][i]), in_queue[G[nodcur][i]].flip();
                                                   

									
									  if(obj_friend[ G[nodcur][i] ])  
															 dw[ G[nodcur][i] ] = 0;
                                      else                    
															 dw[ G[nodcur][i] ] = dw[nodcur]+CW[nodcur][i];
									  
									  
						             }
							 else if(dt[nodcur]+CT[nodcur][i] == dt[ G[nodcur][i] ])
					                     if(dw[nodcur]+CW[nodcur][i] < dw[ G[nodcur][i] ])  
										                   {dw[ G[nodcur][i] ] = dw[nodcur]+CW[nodcur][i];
										                    if(!in_queue[ G[nodcur][i]] )
                                                                     Q.push(G[nodcur][i]), in_queue[G[nodcur][i]].flip();
														   }															
				            }
			  }
	if(dt[N]==INF)  return 0;
    else            return dt[N];	
    }

int binary_chop_W()
	{long long int j, logK, lg,t ;
	
	 for(logK=1;logK<=K;logK<<=1);
	 
	 for(lg=logK,j=0;lg;lg>>=1)
		    if(j+lg<=K)
			    {t=t_bell_f(j+lg);
			     if(t==0 || t>Tmin)
					   j+=lg;
				}
	 return j+1;		
	}
void write()
	{freopen("lanterna.out","w",stdout);  
	
	 Tmin=t_bell_f(K);
	 
	 printf("%d %d\n",Tmin,binary_chop_W());
	 fclose(stdout);
	}
int main()
	{read();
	 write();
	 return 0;
	}