#include <bits/stdc++.h>
using namespace std;
int n, m, ans, W[40 + 5];
vector<int> Vec[40 + 5];
struct Node {
  int last;
  long long sb, sd;
  Node(int _last = 0, long long _sb = 0, long long _sd = 0) {
    last = _last, sb = _sb, sd = _sd;
  }
  bool operator<(const Node a) const {
    if (last < a.last)
      return 1;
    else if (last > a.last)
      return 0;
    if (sb < a.sb)
      return 1;
    else if (sb > a.sb)
      return 0;
    if (sd < a.sd)
      return 1;
    else if (sd > a.sd)
      return 0;
    return 0;
  }
} q[5000000 + 5];
map<Node, int> Map, Dis;
inline void BFS(int st) {
  int l = 1, r = 0, w = W[st];
  long long sb = (1LL << st), sd = sb;
  for (int i = 0; i < Vec[st].size(); i++) {
    int d = Vec[st][i];
    if ((sd & (1LL << d)) == 0) w += W[d];
    sd |= (1LL << d);
  }
  q[++r] = Node(st, sb, sd);
  Dis[q[r]] = w, Map[q[r]] = r;
  while (l <= r) {
    Node x = q[l++];
    Map[x] = 0;
    int w = Dis[x], z = x.last;
    for (int i = 0; i < Vec[z].size(); i++) {
      int d = Vec[z][i];
      if ((x.sb >> d) & 1) continue;
      int _w = w + ((x.sd & (1LL << d)) ? 0 : W[d]);
      long long _sb = x.sb | (1LL << d), _sd = x.sd | (1LL << d);
      for (int j = 0; j < Vec[d].size(); j++) {
        int _d = Vec[d][j];
        if (_sd & (1LL << _d)) continue;
        _sd |= (1LL << _d);
        _w += W[_d];
      }
      if (d == n) ans = min(ans, _w);
      if (_w >= ans) continue;
      Node _x = Node(d, _sb, _sd);
      if (Dis[_x] != 0 && Dis[_x] <= _w) continue;
      Dis[_x] = _w;
      if (!Map[_x]) {
        q[++r] = _x;
        Map[_x] = r;
      }
      if (r > l && Dis[q[r]] < Dis[q[l]]) {
        swap(Map[q[l]], Map[q[r]]);
        swap(q[l], q[r]);
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", W + i);
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d%d", &u, &v);
    Vec[u].push_back(v);
    Vec[v].push_back(u);
  }
  ans = 593119681;
  BFS(1);
  printf("%d\n", ans + 1);
  return 0;
}
