#include <iostream>
#include <vector>
#include <climits>

using namespace std;

int calc(int i, vector<int> &dp, vector<vector<int>> &e, vector<int> &p, vector<char> &vis)
{
    if(dp[i] != INT_MIN || vis[i]) return dp[i];

    int maxj = INT_MIN;
    int jindex;

    for(int j : e[i])
    {
        int dist = calc(j, dp, e, p, vis);

        if(dist > maxj)
        {
            maxj = dist;
            jindex = j;
        }
    }
 
    if(maxj != INT_MIN) dp[i] = maxj + p[i];
    vis[i] = 1;

    return dp[i];
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> p(n + 1);

    for(int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }

    vector<vector<int>> e(n + 1);

    for(int i = 0; i < m; i++)
    {
        int x, y;
        cin >> x >> y;

        e[x].push_back(y);
    }
    
    vector<int> dp(n + 1, INT_MIN);
    dp[n] = p[n];

    vector<char> vis(n + 1);
    vis[n] = 1;

    int eredmeny = calc(1, dp, e, p, vis);

    if(eredmeny == INT_MIN)
    {
        cout << -1;
        
        return 0;
    }else
    {
        cout << eredmeny << "\n";

        int u = 1;

        vector<int> ans;

        while(u != n)
        {
            ans.push_back(u);

            for(int v : e[u])
            {
                if(dp[u] == p[u] + dp[v])
                {
                    u = v;
                    break;
                }
            }
        }

        ans.push_back(n);

        for(int i : ans)
        {
            cout << i << " ";
        }
    }

    return 0;
}