#include <bits/stdc++.h>

using namespace std;
const long long NEG_INF=-1e18;

int main()
{
    int n,m;
    cin>>n>>m;
    vector<int>latvany(n+1);
    for(int i=1; i<=n; i++)
    {
        cin>>latvany[i];
    }

    vector<vector<int>>g(n+1);
    vector<int>utak(n+1,0);

    int u,v;
    for(int i=0; i<m; i++)
    {
        cin>>u>>v;
        g[u].push_back(v);
        utak[v]++;
    }

    queue<int>q;
    for(int i=1; i<=n; i++)
    {
        if(utak[i]==0)
        {
            q.push(i);
        }
    }
    vector<int>top;
    while(!q.empty())
    {
        u=q.front();
        q.pop();
        top.push_back(u);
        for(int v:g[u])
        {
            if(--utak[v]==0)
            {
                q.push(v);
            }
        }
    }
    vector<long long>dp(n+1,NEG_INF);
    vector<int>parent(n+1, -1);
    dp[1]=latvany[1];
    for(int u:top)
    {
        if(dp[u]==NEG_INF)
        {
            continue;
        }
        for(int v:g[u])
        {
            if(dp[v]<dp[u]+latvany[v])
            {
                dp[v]=dp[u]+latvany[v];
                parent[v]=u;
            }
        }
    }
    if(dp[n]==NEG_INF)
    {
        cout<<-1;
        return 0;
    }
    vector<int>ut;
    for(int v=n; v!=-1; v=parent[v])
    {
        ut.push_back(v);
    }
    reverse(ut.begin(),ut.end());
    cout<<dp[n]<<endl;
    for(int x:ut)
    {
        cout<<x<<" ";
    }
    return 0;
}