#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m, n, i, a, b;
    cin >> m >> n;
    int t[n+1], el[n+1], value[n+1];
    bool eler=0;
    vector<vector<int>> vec(n+1);
    for(i=1; i<=n; i++)cin >> t[i];
    for(i=1; i<=n; i++)
    {
        cin >> a >> b;
        vec[a].push_back(b);
        value[i]=0;
    }
    el[1]=-1;
    value[1]=t[1];
    queue<int>q;
    q.push(1);
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        if(a==n)eler=1;
        for(auto &j:vec[a])
        {
            if(value[j]<t[j]+value[a])
            {
                value[j]=t[j]+value[a];
                el[j]=a;
            }
            q.push(j);
        }
    }
    stack<int>st;
    if(eler)
    {
        cout << value[n] << endl;
        a=n;
        while(a!=-1)
        {
            st.push(a);
            a=el[a];
        }
        while(!st.empty())
        {
            cout << st.top() << " ";
            st.pop();
        }
    }
    else cout << -1;

    return 0;
}