// 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);
    vector<int> lat(n),fok(n),fr(n,-1);
    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);
        fok[b]++;
    }
    queue<int> qq;
    qq.push(0);
    vector<int> VIS(n);
    VIS[0]=1;
    while(!qq.empty()){
        int a=qq.front();
        qq.pop();
        for(int u : v[a]){
            if(!VIS[u]){
                VIS[u]=1;
                qq.push(u);
            }
        }
    }
    if(VIS[n-1]==0){
        cout<<-1;return 0;
    }
    //idk miert nem jo ^ nelkul. tul faradt vagyok most ehhez
    vector<int> dp(n,LLONG_MIN),vis(n);
    queue<int> q;
    dp[0]=lat[0];
    vis[0]=1;
    q.push(0);
    for(int i = 1;i<n;i++){
        if(fok[i]==0){
            vis[i]=1;
            q.push(i);
        }
    }
    while(!q.empty()){
        int a=q.front();
        q.pop();
        for(int i : v[a]){
            if(dp[i]<dp[a]+lat[i]){
                dp[i]=dp[a]+lat[i];
                fr[i]=a;
            }
            fok[i]--;
            if(fok[i]==0&&vis[i]==0){
                vis[i]=1;
                q.push(i);
            }
        }
    }
    //for(int i : dp)cout<<i<<' ';return 0;
    if(vis[n-1]==0){
        cout<<-1;
        return 0;
    }
    cout<<dp[n-1]<<endl;
    int i = n-1;
    vector<int> ans;
    while(i!=-1){
        ans.push_back(i+1);
        i=fr[i];
    }
    reverse(ans.begin(),ans.end());
    for(int i : ans)cout<<i<<' ';
}