#include <iostream>
#include <vector>
#include <stdint.h>

using namespace std;

struct Ter {
    vector<int32_t> et;
    //vector<int32_t> ef;
    int32_t n;  // látványosságok száma
    int32_t an = -1; // sok látványosság
    int32_t ob = -1; // előző elem
};


int main(){
    Ter terek[20'000];
    int32_t N, M;
    cin >> N >> M;

    for(int32_t i=0; i<N; i++) cin >> terek[i].n;

    for(int32_t i=0; i<M; i++){
        int32_t t1, t2;
        cin >> t1 >> t2;
        terek[t1-1].et.push_back(t2-1);
        //terek[t2-1].ef.push_back(t1-1);
    }

    terek[0].an = terek[0].n;
    vector<int32_t> q;
    q.push_back(0);
    int32_t si= 0;
    while(si < q.size()){
        for(int32_t&x:terek[q[si]].et){
            q.push_back(x);
            if(terek[x].an < terek[q[si]].an + terek[x].n) {
                terek[x].an = terek[q[si]].an + terek[x].n;
                terek[x].ob = q[si];
            }
        }
        si++;
    }

    vector<int32_t> o1;
    for(int32_t i=N - 1; i != 0; i = terek[i].ob){
        o1.push_back(i+1);
        if(i == -1){
            cout << -1 << endl;
            return 0;
        }
    }
    cout << terek[N - 1].an << endl;
    cout << 1 << " ";
    for(int32_t i = o1.size()-1; i >= 0; i--) cout << o1[i] << " "; 
    cout << endl;

    return 0;
}