#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <climits>
#include <queue>
using namespace std;

int main() {
    ifstream infile("taxi.in");
    ofstream outfile("taxi.out");

    int n, m, count, days;
    infile >> n >> m;
    vector<int> prestige(n);
    vector<pair<int, int>> roads(m);
    vector<int> price(m);

    for (int i = 0; i < n; ++i) {
        infile >> prestige[i];
    }

    for (int i = 0; i < m; ++i) {
        infile >> roads[i].first >> roads[i].second;
        int s = abs(roads[i].first - roads[i].second);
    }

    vector<bool> visited(n + 1, false);
    int curr = 1;
    count = 0;
    days = 1;

    for (int i = 0; i < n; ++i) {
        outfile << prestige[i]<< " ";
    }

    outfile << "\n";

    outfile << days;
   
    outfile << "\n";

    outfile<< curr<< " ";
    while (count < n - 1) {
        int cheapestNext = -1;
        int cheapestCost = INT_MAX;
        bool found = false;

        for (int i = 0; i < m; i++) {
            if (roads[i].first == curr && !visited[roads[i].second]) {
                if (price[i] < cheapestCost) {
                    cheapestCost = price[i];
                    cheapestNext = roads[i].second;
                    found = true;
                }
            } else if (roads[i].second == curr && !visited[roads[i].first]) {
                if (price[i] < cheapestCost) {
                    cheapestCost = price[i];
                    cheapestNext = roads[i].first;
                    found = true;
                }
            }
        }

        if (found) {
            outfile  <<cheapestNext << " ";
            visited[curr] = true;
            curr = cheapestNext;
            count++;
        } else {
            int alternativeCity = -1;
            for (int i = 1; i <= n; ++i) {
                if (i != n ) {
                    alternativeCity = i;
                    break;
                }
            }

            if (alternativeCity != -1) {
                outfile  << alternativeCity << " ";
                visited[curr] = true;
                curr = alternativeCity;
                count++;
                days++;
            } else {
                break;
            }
        }
    }

    outfile  << n << " ";

    infile.close();
    outfile.close();
    return 0;
}