
#include <bits/stdc++.h>

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fr, to)    for (int i = fr; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 40, inf = 0x3f3f3f3f;
int n, m, s = 1, e, cnt[nsz + 5], w[nsz + 5], ans = inf;
vector<int> g[nsz + 5];

void dfs(int u = s, int p = s, int res = w[s]) {
    ++cnt[u];
    for (int v : g[u]) {
        if (!cnt[v]) {
            res += w[v];
        }
        ++cnt[v];
    }
    if (u == e) {
        ans = min(ans, res);
    } else {
        for (int v : g[u]) {
            if (cnt[v] > 1)  continue;
            dfs(v, u, res);
        }
    }
    --cnt[u];
    for (int v : g[u]) {
        --cnt[v];
        if (!cnt[v]) {
            res -= w[v];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    e = n;
    cont (u, n) {
        cin >> w[u];
    }
    cont (i, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs();
    cout << ans << endl;
}


### Prompt

Your task is to create a Cpp solution to the following problem:

Example

Input

6 6
3
1
9
4
3
6
1 2
1 4
2 6
5 4
6 5
3 2


Output

17

### Response

```cpp

#include <bits/stdc++.h>

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fr, to)    for (int i = fr; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

const int nsz = 40, inf = 0x3f3f3f3f;
int n, m, s = 1, e, cnt[nsz + 5], w[nsz + 5], ans = inf;
vector<int> g[nsz + 5];

void dfs(int u = s, int p = s, int res = w[s]) {
    ++cnt[u];
    for (int v : g[u]) {
        if (!cnt[v]) {
            res += w[v];
        }
        ++cnt[v];
    }
    if (u == e) {
        ans = min(ans, res);
    } else {
        for (int v : g[u]) {
            if (cnt[v] > 1)  continue;
            dfs(v, u, res);
        }
    }
    --cnt[u];
    for (int v : g[u]) {
        --cnt[v];
        if (!cnt[v]) {
            res -= w[v];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> m;
    e = n;
    cont (u, n) {
        cin >> w[u];
    }
    cont (i, m) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs();
    cout << ans << endl;
}


```