// Városnézés topologia.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<int> latv(n + 1);
    vector<int> indegree(n + 1,0);
    vector<int> maxlatv(n + 1,-1);
    vector<int>honnan(n + 1);
    honnan[1] = -1;
    for (int i = 1; i <= n; i++)
    {
        int x; cin >> x;
        latv[i] = x;
    }
    maxlatv[1] = latv[1];
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        indegree[y]++;
    }
    queue<int> q;
    q.push(1);
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (auto next : adj[v])
        {
            indegree[next]--;
            if (maxlatv[v] + latv[next] > maxlatv[next])
            {
                maxlatv[next] = maxlatv[v] + latv[next];
                honnan[next] = v;
            }
            if (indegree[next] == 0)
            {
                q.push(next);
            }
        }
    }
    cout << maxlatv[n] << endl;
    if(maxlatv[n]!=-1)
    {
        int x = honnan[n];
        vector<int>res;
        res.push_back(n);
        while (x != -1)
        {
            res.push_back(x);
            x = honnan[x];
        }
        reverse(res.begin(), res.end());
        for (auto x : res)
            cout << x << " ";
    }
}