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


vector<vector<int>> b, odaut;
vector<int> a, megtekintlat;
vector<bool> voltmarott;
bool ellehet_e = false;
int n;

int gbj(int start)
{
	if (start == n)
	{
		ellehet_e = true;
		odaut[start].push_back(start);
		return a[n];
	}
	else if (!b[start].size())
		return -1;

	int max = 0, maxi;
	voltmarott[start] = true;
	for (int i = 0; i < b[start].size(); i++)
	{
		if (voltmarott[b[start][i]])
		{
			if (megtekintlat[b[start][i]] > max)
			{
				max = megtekintlat[b[start][i]];
				maxi = i;
			}
		}
		else
		{
			int x = gbj(b[start][i]);
			if (x > max)
			{
				max = x;
				maxi = i;
			}
		}
	}
	if (max > 0)
	{
		odaut[start].push_back(start);
		for (int i = 0; i < odaut[b[start][maxi]].size(); i++)
		{
			odaut[start].push_back(odaut[b[start][maxi]][i]);
		}
	}
	megtekintlat[start] = max + a[start];
	return max + a[start];
}


int main()
{
	int m;
	cin >> n >> m;

	a.resize(n + 1);
	for (int i = 1; i < n + 1; i++)
		cin >> a[i];

	b.resize(n + 1, vector<int>());
	megtekintlat.resize(n + 1, -1);
	voltmarott.resize(n + 1, false);
	odaut.resize(n + 1);

	for (int i = 1; i < m + 1; i++)
	{
		int temp1, temp2;
		cin >> temp1 >> temp2;
		b[temp1].push_back(temp2);
	}

	cout << gbj(1);
	if (ellehet_e)
	{
		cout << "\n";
		for (int i = 0; i < odaut[1].size(); i++)
		{
			cout << odaut[1][i] << " ";
		}
	}
}