QBROBOT

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 505;
const int oo = 5e6 + 5;

int n, m;
int g[N], Time[N][N], Cost[N][N];
int64_t d[N];
vector<int> a[N];

void Dijkstra() {
    priority_queue<pair<int, int64_t> > pq;

    fill(d + 1, d + n + 1, oo);
    d[n] = 0;
    pq.push({d[n], n});

    while(!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();

        if(du > d[u]) continue;

        for(int v : a[u]) {
            if(d[v] > d[u] + Time[u][v]) {
                d[v] = d[u] + Time[u][v];
                pq.push({d[v], v});
            }
        }
    }
}

struct edge {
    int root, timer, costs;
};

bool check(int mid) {
    queue<edge> pq;
    pq.push({1, 0, mid});

    while(!pq.empty()) {
        int u = pq.front().root;
        int tu = pq.front().timer;
        int wu = pq.front().costs;
        pq.pop();

        for(int v : a[u]) {
            if(wu < Cost[u][v]) continue;
            if(tu + Time[u][v] + d[v] > d[1]) continue;

            int wv = g[v] ? mid : wu - Cost[u][v];
            int tv = tu + Time[u][v];

            if(v == n && tv == d[1])
                return true;

            pq.push({v, tv, wv});
        }
    }
    return false;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("ROBOT.inp", "r", stdin);
    //freopen("ROBOT.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> g[i];
    cin >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, t, c;
        cin >> u >> v >> t >> c;

        a[u].push_back(v);
        a[v].push_back(u);
        Time[u][v] = Time[v][u] = t;
        Cost[u][v] = Cost[v][u] = c;
    }

    Dijkstra();

    int64_t L = 1, R = oo, ans = 0;
    while(L <= R) {
        int mid = (L+R) / 2;
        if(check(mid))
            ans = mid, R = mid - 1;
        else
            L = mid + 1;
    }

    cout << ans << '\n';

    return 0;
}