// Source: https://usaco.guide/general/io

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

signed main() {
    int n,m;cin>>n>>m;
    vector<vector<int>> v(n),g(n);
    vector<int> lat(n),fok(n),fr(n);
    for(int i = 0;i<n;i++){
        cin>>lat[i];
    }
    for(int i = 0;i<m;i++){
        int a,b;cin>>a>>b;
        a--;b--;
        v[a].push_back(b);
        g[b].push_back(a);
        fok[a]++;
    }
    vector<int> dp(n,-1),vis(n);
    queue<int> q;
    for(int i = 0;i<n;i++){
        if(fok[i]==0&&i!=n-1){
            vis[i]=1;
            q.push(i);
            dp[i]=-2;
        }
        else if(fok[i]==0&&i==n-1){
            vis[i]=1;
            dp[i]=lat[i];
            q.push(i);
        }
    }
    int cntt=0;
    while(!q.empty()){
        cntt++;
        if(cntt>n){
            cout<<-1;return 0;
        }
        int a=q.front();
        q.pop();
        if(dp[a]!=-2&&a!=n-1){
            for(int u:v[a]){
                if(dp[a]<dp[u]&&vis[u]){
                    dp[a]=max(dp[a],dp[u]);
                    fr[a]=u;
                }
            }
            dp[a]+=lat[a];
        }
        for(int u : g[a]){
            fok[u]--;
            if(fok[u]==0&&vis[u]==0){
                vis[u]=1;
                q.push(u);
            }
        }
    }
    //for(int i : fr)cout<<i<<' ';return 0;
    if(dp[0]<0){
        cout<<-1;
        return 0;
    }
    cout<<dp[0]<<endl;
    int i = 0;
    vector<int> ans;
    int cnttt=0;
    while(fr[i]!=0){
        cnttt++;
        if(cnttt>n){
            cout<<-1;return 0;
        }
        ans.push_back(i+1);
        i=fr[i];
    }
    ans.push_back(n);
    for(int i : ans)cout<<i<<' ';
}