from sys import stdin,setrecursionlimit
input=stdin.readline
setrecursionlimit(10**6)

def solv():
    N,M = map(int,input().split())
    P = [0]+list(map(int,input().split()))
    G = [set() for i in range(N+1)]
    Ginv = [set() for i in range(N+1)]
    for i in range(M):
        x,y = map(int,input().split())
        G[x].add(y)
        Ginv[y].add(x)
    visited={N}
    cur=[N]
    while cur:
        tmp=set()
        for v in cur:
            for w in Ginv[v]:
                if w not in visited:
                    tmp.add(w)
                    visited.add(w)
        cur=tmp
    if 1 not in visited:
        print(-1)
        return
    #print(visited,Ginv)
    for v in visited:
        tmp=[]
        for w in G[v]:
            if w not in visited:
                tmp.append(w)
        for w in tmp:
            G[v].remove(w)
    #print(G)
    res=[0]*(N+1)
    reached=[False]*(N+1)
    res[N]=P[N]
    reached[N]=True
    cur=[N]
    def rek(i):
        cur=-1
        for v in G[i]:
            if reached[v]:
                cur=max(cur,res[v]+P[i])
            else:
                rek(v)
                cur=max(cur,res[v]+P[i])
        reached[i]=True
        res[i]=cur
    rek(1)
    """
    while cur:
        tmp=set()
        for v in cur:
            if reached[v]<len(G[v]):
                tmp.add(v)
                continue
            for w in Ginv[v]:
                res[w]=max(res[w],res[v]+P[w])
                reached[w]+=1
                tmp.add(w)
        cur=tmp
    """
    print(res[1])
    RES=[1]
    while RES[-1]!=N:
        for v in G[RES[-1]]:
            if res[v]+P[RES[-1]]==res[RES[-1]]:
                RES.append(v)
                break
    print(*RES)

solv()