#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll,ll>;
using vll = vector<ll>;
using vi = vector<int>;
using pi = pair<int, int>;
using vpi = vector<pair<int, int>>;
using vai = vector<array<int, 3>>;

#define x first
#define y second
#define all(x) x.begin(), x.end()

int n;
vi dp, v, res;
int resi;
vector<vi> connect;
void dfs(vi &ans, int node, int pont) {
    pont += v[node];
    if (node == n-1) {
        if (resi < pont) {
            res = ans;
            resi = pont;
        } return;
    }
    if (dp[node] < pont) {
        for (int i : connect[node]) {
            ans.push_back(node);
            dfs(ans, i, pont);
            ans.pop_back();
        }
    }
}

void solve() {
    int m; cin >> n >> m;
    v.resize(n); for (auto &i : v) cin >> i;
    dp.resize(n, -1);
    connect.resize(n);
    for (int i = 0; i < n; i++) {
        int u, w; cin >> u >> w;
        u--; w--;
        connect[u].push_back(w);
    }

    vi ans;
    dfs(ans, 0, 0);

    cout << resi << "\n";
    for (int i = 0; i < res.size(); i++) {
        cout << res[i]+1 << " ";
    } cout << n;
}

int main() {
	ios::sync_with_stdio(0);
    cin.tie(0);

    int t=1;
    //cin >> t;
    while (t--) {
        solve();
    }
}