#include <bits/stdc++.h>

using namespace std;

int N,M;



int main(){
    cin>>N>>M;
    vector<int> P(N + 1); // látványosságok száma
    for (int i = 1; i <= N; i++) cin >> P[i];
    vector<vector<int>> adj(N + 1);
    vector<int> indeg(N + 1, 0);
    
    for (int i = 0; i < M; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].push_back(v);
    indeg[v]++;
}
    queue<int> q;
    for (int i = 1; i <= N; i++){   
    if (indeg[i] == 0) q.push(i);
    }
    vector<int> topo;
while (!q.empty()) {
    int u = q.front(); q.pop();
    topo.push_back(u);
    for (int v : adj[u]) {
        indeg[v]--;
        if (indeg[v] == 0) q.push(v);
    }
}

vector<long long> dp(N + 1, LLONG_MIN);
vector<int> par(N + 1, -1);
dp[1] = P[1];
for (int u : topo) {
    if (dp[u] == LLONG_MIN) continue; // nem elérhető
    for (int v : adj[u]) {
        if (dp[v] < dp[u] + P[v]) {
            dp[v] = dp[u] + P[v];
            par[v] = u;
        }
    }
}
if (dp[N] == LLONG_MIN) {
    cout << -1 << "\n";
} else {
    cout << dp[N] << "\n";
    vector<int> path;
    for (int cur = N; cur != -1; cur = par[cur])
        path.push_back(cur);
    reverse(path.begin(), path.end());
    for (int i = 0; i < path.size(); i++) {
        if (i) cout << " ";
        cout << path[i];
    }
    cout << "\n";
}

    return 0;
};