#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()

using namespace std;
using vi = vector<int>;

constexpr int ms = 413;
constexpr int inf = 0x3f3f3f3f;

int dp[2][ms][ms];

int main()
{

    memset( dp, inf, sizeof(dp) );
    ios::sync_with_stdio( false ); cin.tie( nullptr );
    int n, m;
    cin >> n >> m;
    vector< int > temperature( n );
    for(int& t : temperature ) cin >> t;

    for(int i = 0; i < m; ++i)
    {
        int a, b, d;
        cin >> a >> b >> d;
        --a, --b;
        dp[0][a][b] = dp[0][b][a] = dp[1][a][b] = dp[1][b][a] = min( dp[0][a][b], d );
    }

    int q;
    cin >> q;

    deque< tuple<int, int, int, int> > Q[2];

    for(int i = 0; i < q; ++i)
    {
        int a, b, k, t;
        cin >> a >> b >> k >> t;
        Q[t].emplace_back(k, a - 1, b - 1, i);
    }

    for(int i = 0; i < 2; ++i) sort( all(Q[i] ) );

    vector< vi > nodes_by_k[2];

    vector< int > ans(q, -1);

    for(int i = 0; i < 2; ++i) nodes_by_k[i].resize( n + 1 );

    vector< int > cpy = temperature;
    sort( all(cpy) );
    cpy.erase( unique( all(cpy) ), cpy.end() );
    vector< int > cpy2 = cpy;
    reverse( all(cpy2) );


    for(int i = 0; i < n; ++i)
    {
        int tmp = temperature[i];
        int i_k = lower_bound( all(cpy), tmp ) - cpy.begin() + 1;
        nodes_by_k[0][i_k].push_back( i );
        i_k     = lower_bound( all(cpy2), tmp, [] ( const int& a, const int& b) { return a > b; } ) - cpy2.begin() + 1;
        nodes_by_k[1][i_k].push_back( i );
    }


    for(int z = 0; z <= n; ++z)
    {
        vector< tuple<int, int, int> > go[2];
        for(int i = 0; i < 2; ++i)
        {
            while( !Q[i].empty() && get<0>(Q[i].front() ) == z )
            {
                go[i].emplace_back( get<1>(Q[i].front() ), get<2>(Q[i].front() ), get<3>(Q[i].front()) );
                Q[i].pop_front();
            }

            for(const auto& piv : nodes_by_k[i][z] )
            {
                for(int x = 0; x < n; ++x)
                {
                    for(int y = 0; y < n; ++y)
                    {
                        if( dp[i][x][piv] != inf && dp[i][piv][y] != inf )
                        {
                            dp[i][x][y] = min( dp[i][x][y], dp[i][x][piv] + dp[i][piv][y] );
                        }
                    }
                }
            }
        }
        for(int i = 0; i < 2; ++i)
        {
            for( const auto& qry : go[i] )
            {
                int u = get<0>(qry), v = get<1>(qry), id = get<2>(qry);
                ans[ id ] = dp[i][u][v];
            }
        }
    }
    for(int i = 0; i < q; ++i) cout << ( ans[i] == inf ? -1 : ans[i] ) << endl;
    return 0;

}