#include <bits/stdc++.h>
using namespace std;
const char dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
bool find(long long source, int n) { return source & (1ll << n); }
long long add(long long &source, int n) {
  source |= (1ll << n);
  return source;
}
long long erase(long long &source, int n) {
  source &= ~(1ll << n);
  return source;
}
pair<pair<long, long>, pair<long, long> > mp(long long a, long long b,
                                             long long c, long long d) {
  return pair<pair<long, long>, pair<long, long> >(pair<long, long>(a, b),
                                                   (pair<long, long>(c, d)));
}
int main() {
  int n, m;
  cin >> n >> m;
  vector<int> c(n), v(n);
  vector<vector<int> > edge(n);
  for (int i = 0; i < (n); i++) cin >> c[i];
  for (int i = 0; i < (m); i++) {
    int s, t;
    cin >> s >> t;
    edge[--s].push_back(--t);
    edge[t].push_back(s);
  }
  long long sp = 0;
  int second = c[0];
  for (int i = 0; i < (edge[0].size()); i++) {
    int t = edge[0][i];
    if (!find(sp, t)) {
      add(sp, t);
      second += c[t];
    }
  }
  priority_queue<pair<pair<long, long>, pair<long, long> > > q;
  q.push(mp(-second, 1ll, sp, 0));
  while (!q.empty()) {
    int cost = -q.top().first.first;
    long long path = q.top().first.second;
    long long adj = q.top().second.first;
    int node = q.top().second.second;
    q.pop();
    if (v[node]) continue;
    v[node] = cost;
    for (int i = 0; i < (edge[node].size()); i++) {
      long long p = path, a = adj;
      int cst = cost;
      int t = edge[node][i];
      if (!find(p, t)) {
        if (find(a, t)) {
          erase(a, t);
        } else {
          cst += c[t];
        }
        add(p, t);
      }
      for (int j = 0; j < (edge[t].size()); j++) {
        int u = edge[t][j];
        if (!find(p, u) && !find(a, u)) {
          add(a, u);
          cst += c[u];
        }
      }
      for (int j = 0; j < (edge[t].size()); j++) {
        q.push(mp(-cst, p, a, edge[t][j]));
      }
    }
  }
  cout << v[n - 1] << endl;
  return 0;
}
