#include <bits/stdc++.h>
using namespace std;
const int maxn = 66;
vector<int> e[maxn];
int n, m;
int c[maxn];
int g[maxn * maxn][2];
int d[maxn];
int u[maxn];
struct node {
  long long maze;
  int cost, now;
  bool operator<(const node &b) const { return cost < b.cost; }
};
multiset<node> Q;
void Bfs() {
  int temp = c[1];
  long long buf = 1;
  for (auto i : e[1]) {
    temp += c[i];
  }
  Q.insert({buf, temp, 1});
  while (1) {
    node X = *Q.begin();
    if (X.now == n) {
      cout << X.cost << endl;
      return;
    }
    Q.erase(Q.begin());
    node Y = X;
    for (auto i : e[X.now]) Y.maze |= (1 << (i - 1));
    for (auto i : e[X.now])
      if (((1 << (i - 1)) | X.maze) != X.maze) {
        Y.now = i;
        Y.cost = X.cost;
        for (auto j : e[i]) {
          if (((1 << (j - 1)) | Y.maze) != Y.maze) Y.cost += c[j];
        }
        Q.insert(Y);
      }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) scanf("%d", &c[i]);
  for (int i = 1; i <= m; ++i) {
    int x, y;
    scanf("%d%d", &x, &y);
    e[x].push_back(y);
    e[y].push_back(x);
    g[i][0] = x;
    g[i][1] = y;
  }
  for (int i = 1; i < n; ++i) d[i] = 101 * n;
  d[n] = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) {
      int x = g[j][0];
      int y = g[j][1];
      d[x] = min(d[x], d[y] + c[y]);
      d[y] = min(d[y], d[x] + c[x]);
    }
  u[n] = 0;
  for (int i = 1; i < n; ++i) {
    u[i] = 101 * n;
    for (auto j : e[i]) u[i] = min(u[i], d[j]);
  }
  Bfs();
}
