//#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge 
{
  int cost, dest;
  Edge(int c, int d) : cost(c), dest(d) {}
};

int main()
{
  int n, I = 0;
  for(cin >> n; n > 0; --n)
  {
    int p, c; cin >> p >> c;
    //cout << "XXX" << p << ' ' << c << endl;
    vector<vector<Edge> > map(p + 1);
    for(int i = 0; i < p; ++i)
    {
      int cost; cin >> cost;
      map[p].push_back(Edge(cost, i));
    }
    for(int k = 0; k < c; ++k)
    {
      int i,j,a,b; cin >> i >> j >> a >> b;
      map[i].push_back(Edge(a, j));
      map[j].push_back(Edge(b, i));
    }
    typedef pair<int, int> Label;
    priority_queue<Label, vector<Label>, greater<Label> > pq;
    pq.push(make_pair(0,p));
    
    vector<bool> visited(p + 1, false);
    
    int last, lastCost;
    while(!pq.empty())
    {
      Label l = pq.top();
      pq.pop();
      if(visited[l.second])
        continue;
      
      if(l.first == lastCost)
        last = min(last, l.second);
      else
      {
        last = l.second;
        lastCost = l.first;
      }
        
      visited[l.second] = true;
      
      for(unsigned int i = 0; i < map[l.second].size(); ++i)
        if(!visited[map[l.second][i].dest])
          pq.push(make_pair(l.first + map[l.second][i].cost, 
                            map[l.second][i].dest));
    }
    cout << "Scenario #" << ++I << ":\n";
    cout << last << endl << /*lastCost << endl <<*/ endl;
  }
  return 0;
}
