import java.util.*;

class node implements Comparable<node>
{
  public Vector<Integer> edges = new Vector<Integer>();
  public Vector<Integer> costs = new Vector<Integer>();
  int best = Integer.MAX_VALUE;
  boolean visited = false;

  public int index;

  public void add(int to, int cost) {
    edges.add(to);
    costs.add(cost);
  }

  public int compareTo(node b) {
    return best - b.best;
  }

  public String toString() {
    return "" + best;
  }
}

class Solution
{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();
    for (int I = 1; I <= N; ++I) {

      int p = sc.nextInt(), c = sc.nextInt();

      node[] nodes = new node[p + 1];
      for (int i = 0; i <= p ; ++i) nodes[i] = new node();
      for (int i = 0; i <= p ; ++i) nodes[i].index = i;

      for (int i = 0; i < p; ++i)
        nodes[0].add(i+1, sc.nextInt());
      nodes[0].best = 0;

      for (int i = 0; i < c; ++i) {
        int ii = sc.nextInt(), ji = sc.nextInt();
        nodes[ii+1].add(ji+1, sc.nextInt());
        nodes[ji+1].add(ii+1, sc.nextInt());
      }

      PriorityQueue<node> q = new PriorityQueue<node>();
      q.add(nodes[0]);
      while (!q.isEmpty()) {
        node curr = q.poll();
        if (nodes[curr.index].visited) continue;

        //System.out.println("XXX:" + curr.index + "   " + curr.best);

        nodes[curr.index].visited = true;
        for (int i = 0; i < curr.edges.size(); ++i) {
          node to = nodes[curr.edges.get(i)];
          int newBest = curr.best + curr.costs.get(i);
          if (newBest < to.best) {

            // changing the sorting key of an element in a pq is a bad idea,
            // create a new object for the new cost
            node newNode = new node();
            newNode.edges = to.edges;
            newNode.costs = to.costs;
            newNode.index = to.index;
            newNode.best = newBest;

            // also update cost in array
            nodes[to.index].best = newBest;

            q.add(newNode);

            //System.out.println("YYY:" + newBest + " " + curr.edges.get(i));
          }
        }
      }

      //System.out.println(Arrays.toString(nodes));
      int max = nodes[1].best, bestIndex = 1;
      for (int i = 2; i <= p; ++i) {
        if (nodes[i].best > max) {
          max = nodes[i].best;
          bestIndex = i;
        }
      }
      System.out.println("Scenario #" + I + ":");
      System.out.println(bestIndex-1);
      //System.out.println(max);
      System.out.println();
    }
  }
}

