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

const int NEG=-1e9;

int n;
vector<vector<int>> graf;
vector<int> dp,c,to;
vector<bool> vis;

void dfs(int u){
    vis[u]=1; dp[u]=NEG;
    if (u==n-1){dp[u]=c[u]; return;}
    for (int v:graf[u]){
        if (!vis[v]) dfs(v);
        if (dp[v]!=NEG && dp[u]<dp[v]+c[u]){
            dp[u]=dp[v]+c[u];
            to[u]=v;
        }
    }
}

int main(){
    int m; cin >> n >> m;
    c.resize(n); graf.resize(n); vis.resize(n,0); dp.resize(n,0); to.resize(n,-1);
    for (int i=0;i<n;i++){
        cin >> c[i];
    }
    for (int i=0;i<m;i++){
        int u,v; cin >> u >> v;
        graf[u-1].push_back(v-1);
    }
    dfs(0);

    if(dp[0]<0){
        cout << -1;
        return 0;
    }
    cout << dp[0] << '\n';

    int j=0;
    while(j!=n-1){
        cout << j+1 << ' ';
        j=to[j];
    }
    cout << n;
}