// varosnezes.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <list>
using namespace std;

struct adat {
    int csp;
    vector<int>sz;
    int lat, latv_sz;
};

vector<adat>x;
vector<pair<int, int>>y;
list<int>sol;

int n, m;

void solve(int akt)
{
    sol.push_front(akt);
    if(y[akt].first != 0) solve(y[akt].first);
}

int main()
{
    cin >> n >> m;
    x.resize(n + 1);
    y.resize(n + 1);
    for (int i = 1; i <= n; ++i)
    {
        cin >> x[i].latv_sz;
    }
    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        x[a].sz.push_back(b);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (i == 1)
        {
            y[i].first = 0;
            y[i].second = x[i].latv_sz;
        }
        else
        {
            y[i].first = 0;
            y[i].second = INT_MIN;
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (auto& e : x[i].sz)
        {
            if (y[e].second <= y[i].second + x[e].latv_sz) //!
            {
                y[e].second = y[i].second + x[e].latv_sz;
                y[e].first = i;
            }
        }
    }

    if (y[n].second != INT_MIN)
    {
        cout << y[n].second << endl;
        solve(n);
        for (auto& e : sol) cout << e << " ";
    }
    else
    {
        cout << -1;
    }
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file