#include <fstream>
#include <stack>
#include <vector>
using namespace std;

ifstream in("activitati.in");
ofstream out("activitati.out");
bool ok;
int maxx, id;

vector<int> from;
vector<int> durata;
vector<int> durata_max;
vector<vector<int>> graph;

void afis(int k){
    if(from[k] != 0)
        afis(from[k]);
    out << k << ' ';
}


//Sortare topologica!

void dfs(vector<vector<int>> &graph, vector<int> &visited, stack<int> &s, int k){
    visited[k] = 1;
    for (auto x : graph[k]) {
        if(visited[x] == 0)
            dfs(graph, visited, s, x);
    }
    s.push(k);
}

void findTime(int n, vector<vector<int>>& graph) {
    vector<int> v(n+1, 0);
    stack<int> s;
    for(int i = 1; i <= n; ++i)
        if(!v[i])
            dfs(graph, v, s, i);
    while (!s.empty()) {            // in stack am sortarea topologica
        int k = s.top();
        for (auto x : graph[k]) {       //  actualizez valoarea vecinilor lui k
            if (durata_max[x] < durata_max[k] + durata[x]) {        // doar daca valoarea noua este mai mare
                durata_max[x] = durata_max[k] + durata[x];
                from[x] = k;                                        //  vector de tati
            }
            if(maxx < durata_max[x]){
                id = x;                     //  retin nodul cu valoarea cea mai mare
                maxx = durata_max[x];       //  retin aparitia maxima
            }
        }
        s.pop();
    }
}

int n, m;

int main() {
    in >> n;
    durata.resize(n+1);
    durata_max.resize(n+1);
    graph.resize(n+1);
    from.resize(n+1, 0);
    for(int i = 1; i <= n; ++i) {
        in >> durata[i];
        durata_max[i] = durata[i];
    }

    in >> m;
    int x, y;
    for(int i = 0; i < m; ++i)
        in >> x >> y, graph[x].push_back(y);

    findTime(n, graph);
    out << durata_max[id] << '\n';

    afis(id);
    out << '\n';
    for(int i = 1; i <= n; ++i){
        out << i << ": " << durata_max[from[i]] << ' ';
        out << durata_max[i] << '\n';
    }

    return 0;
}