#include <bits/stdc++.h>
using namespace std;
struct ter{vector<int>kim; int lat,elo;
    long long ert=0;};
int n,m; vector<ter>a;
int main()
{
    //ifstream f("szamok.txt");
    cin>>n>>m; a.resize(n+1);
    for(int i=1; i<=n; i++)cin>>a[i].lat;
    for(int i=0; i<m; i++){
        int x,y; cin>>x>>y;
        a[x].kim.push_back(y);}
    queue<int>q; q.push(1); a[1].ert=a[1].lat;
    while(!q.empty()){
        int r=q.front();
        for(int i:a[r].kim){
            if(a[i].ert<a[r].ert+a[i].lat){
                a[i].ert=a[r].ert+a[i].lat;
                q.push(i); a[i].elo=r;}}
        q.pop();}
    cout<<a[n].ert<<endl; int t=n; vector<int>ut;
    ut.push_back(n);
    while(t!=1){
        t=a[t].elo;
        ut.push_back(t);}
    for(int i=ut.size()-1; i>=0; i--)cout<<ut[i]<<" ";
    return 0;
}