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

using namespace std;

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

    int maxj = INT_MIN;
    int jindex = -1;

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

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

    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);
    vector<vector<int>> to(n + 1);

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

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

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

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

        int v = n;

        vector<int> ans;

        while(v != 1)
        {
            ans.push_back(v);

            int maxfrom = INT_MIN;
            int maxindex;

            for(int u : to[v])
            {
                if(dp[u] > maxfrom)
                {
                    maxfrom = dp[u];
                    maxindex = u;
                }
            }

            v = maxindex;
        }

        ans.push_back(1);

        for(int i = (int)ans.size() - 1; i >= 0; i--)
        {
            cout << ans[i];
        }
    }

    return 0;
}