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

vector<vector<pair<int,int>>> graph;
vector<int> maxs;
priority_queue<pair<int,pair<int,int>>> help; //.first= weight , .second.first father .second.second destination
vector<int> parent;

void djikstra(int s)
{
for(auto x : graph[s])
    {
    help.push({x.first,{s,x.second}});
    }
int prev=s;
while(!help.empty())
    {
    int v=help.top().second.second;
    //cout<<v<<" "<<maxs[v]<<" "<<prev<<" "<<maxs[prev]<<" "<<help.top().first<<"          ";
    //maxs[v]=max(maxs[v],maxs[help.top().second.first]+help.top().first);
    if(maxs[v]<maxs[help.top().second.first]+help.top().first)
        {
        maxs[v]=maxs[help.top().second.first]+help.top().first;
        parent[v]=help.top().second.first;
        }
    //cout<<v<<" "<<maxs[v]<<" "<<prev<<" "<<maxs[prev]<<" "<<help.top().first<<endl;
    //prev=v;
    help.pop();
    for(auto x : graph[v])
        {
        help.push({x.first,{v,x.second}});
        }
    }
}


int main()
{
    int n,m;
    cin>>n>>m;
    graph.resize(n+1);
    maxs.resize(n+1,-1);
    parent.resize(n+1,-1);
    vector<int> weights(n+1);
    for(int i=1;i<=n;i++)
        {
        cin>>weights[i];
        }
    int x,y;
    for(int i=1;i<=m;i++)
        {
        cin>>x>>y;
        graph[x].push_back({weights[y],y});
        }
    maxs[1]=weights[1];
    djikstra(1);
    cout<<maxs[n]<<endl;
    int i=n;
    if(maxs[n]==-1)
        {

        return 0;
        }
    vector<int> ans;
    ans.push_back(n);
    while(parent[i]!=-1)
        {
        ans.push_back(parent[i]);
        i=parent[i];
        }
    for(int i=ans.size()-1;i>-1;i--)
        {
        cout<<ans[i]<<" ";
        }
    return 0;
}