#include <bits/stdc++.h>

using namespace std;
#define INF INT_MAX;

const int MAX1 = 5010;
const int MAX2 = 110;
int belongs[MAX1];
string cities;
vector<vector<pair<int,int>>> graphDijkstra;
vector<vector<int>> graph;
vector<int> dist, path;
int residualGraph[MAX1][MAX1];
int totalPlaces, nOfCities, nOfRoads, source, to;

bool bfs(int parent[]) {
    bool visited[MAX1] = {false};
    queue<int> q;
    q.push(source);
    visited[source] = true;
    parent[source] = -1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v = 0; v < MAX1; v++) {
            if (!visited[v] and residualGraph[u][v] > 0) {
                q.push(v);
                parent[v] = u;
                visited[v] = true;
            }
        }
    }
    return visited[to];
}

int fordFulkerson() {
    int u, v;
    int parent[MAX1];
    int maxFlow = 0;
    while (bfs(parent)) {
        int pathFlow = INT_MAX;
        for (v = to; v != source; v = parent[v]) {
            u = parent[v];
            pathFlow = min(pathFlow, residualGraph[u][v]);
        }
        for (v = to; v != source; v = parent[v]) {
            u = parent[v];
            residualGraph[u][v] -= pathFlow;
            residualGraph[v][u] += pathFlow;
        }
        maxFlow += pathFlow;
    }
    return maxFlow;
}

int dijkstra() {
    int s = belongs[source];
    int t = belongs[to];
    path.resize(MAX2);
    dist.resize(MAX2);
    for (int i = 0; i < dist.size(); i++) {
        dist[i] = INF;
    }
    dist[source] = 0;
    priority_queue<pair<int,int>> pq;
    dist[source] = 0;
    cout << "coiroi\n";
    path[source] = -1;
    pq.push({0, source});
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();
        for (pair<int,int> p : graphDijkstra[u]) {
            if (dist[u] + p.second < dist[p.first]) {
                dist[p.first] = dist[u] + p.second;
                path[p.first] = u;
                pq.push({-dist[p.first], p.first});
            }
        }
    }
    return dist[t];
}

int main() {
    cin >> totalPlaces;
    cin >> nOfCities;
    cout << "TOTALPLACES = " << totalPlaces << " and NOFCITIES = " << nOfCities << endl;
    char lixo;
    scanf("%c",&lixo);
    for (int i = 0; i < nOfCities; i++) {
        getline(cin, cities);
        cout << cities << endl;
        int n = 0;
        for (int j = 0; cities[j]; j++) {
            if (cities[j] == ' ') {
                belongs[n] = i;
                n = 0;
            } else {
                n = n * 10 + (cities[j] - '0');
            }
        }
        belongs[n] = i;
    }
    cin >> nOfRoads;
    cout << "NOFROADS = " << nOfRoads << endl;
    graph.resize(MAX1);
    graphDijkstra.resize(MAX2);
    for (int i = 0; i < nOfRoads; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        cout << u << " " << v << " " << c << " " << d << endl;
        graph[u].push_back(v);
        graph[v].push_back(u);
        residualGraph[u][v] += c;
        if (belongs[u] != belongs[v]) {
            graphDijkstra[belongs[u]].push_back({belongs[v], d});
        }
    }
    cin >> source >> to;
    cout << "SOURCE = " << source << " and TO = " << to << endl;
    cout << dijkstra() << endl;
    cout << fordFulkerson() << endl;
    return 0;
}