#include <bits/stdc++.h>

using namespace std;

#define TRACE(x) x
#define WATCH(x) TRACE( cout << #x" = " << x << endl)
#define PRINT(x) TRACE(printf(x))
#define WATCHR(a, b) TRACE( for(auto c = a; c != b;) cout << *(c++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end()); } )

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define sz(v) (int) (v).size()
#define rep(i,a,b) for(int (i) = (a); (i) < (b); ++(i))
#define pb push_back
#define mp make_pair

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

constexpr int inf = 0x3f3f3f3f;
constexpr ll MOD = 1000000007LL;
constexpr double tol = 1e-8;

void buff() { ios::sync_with_stdio( false ); cin.tie(nullptr); }

constexpr int ms = 413;

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

int main()
{
    memset( dp, inf, sizeof(dp) );

    buff();
    int n, r;
    cin >> n >> r;

    vector< int > t(n);

    for(int& x : t) cin >> x;

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

    for(int i = 0; i < n; ++i) dp[0][i][i][0] = dp[1][i][i][0] = 0;

    vector< int > nodes(n, 0); iota(all(nodes), 0 );
    sort( all(nodes), [&] ( const int& a, const int& b ) { return t[a] < t[b]; });

    // Tratando empates
    vector< vi > kth_smallest;
    vector< vi > kth_largest;
    vector< int > cur_group = { nodes[0] };

    for(int i = 1; i < n; ++i)
    {
        if( t[ nodes[i] ] == t[ nodes[i - 1] ] )
        {
            cur_group.push_back( nodes[i] );
        }
        else
        {
            kth_smallest.push_back( cur_group );
            cur_group.clear();
            cur_group.push_back( nodes[i] );
        }
    }

    kth_smallest.push_back( cur_group );

    cur_group.clear();
    cur_group.push_back( nodes[ n - 1] );

    for(int i = n - 2; i >= 0; --i)
    {
        if( t[nodes[i]] == t[nodes[i + 1]] )
        {
            cur_group.push_back( nodes[i] );
        }
        else
        {
            kth_largest.push_back( cur_group );
            cur_group.clear();
            cur_group.push_back( nodes[i] );
        }
    }
    kth_largest.push_back( cur_group );
    // Fim do tratamento de empates

    int distinct = sz(kth_largest);
    for(int z = 0; z < n; ++z)
    {
        for(int x = 0; x < n; ++x)
        {
            for(int y = 0; y < n; ++y)
            {
                dp[0][x][y][z + 1] = dp[0][x][y][z];
                dp[1][x][y][z + 1] = dp[1][x][y][z];
            }
        }

        if( z < distinct )
        {
            for(int& node : kth_largest[z] )
            {
                for(int x = 0; x < n; ++x)
                {
                    for(int y = 0; y < n; ++y )
                    {
                        if( dp[1][x][node][z + 1] != inf && dp[1][node][y][z + 1] != inf )
                        {
                            dp[1][x][y][z + 1] = min( dp[1][x][y][z + 1], dp[1][x][node][z + 1] + dp[1][node][y][z + 1] );
                        }
                    }
                }
            }
            for(int& node : kth_smallest[z] )
            {
                for(int x = 0; x < n; ++x)
                {
                    for(int y = 0; y < n; ++y)
                    {
                        if( dp[0][x][node][z + 1] != inf && dp[0][node][y][z + 1] != inf )
                        {
                            dp[0][x][y][z + 1] = min( dp[0][x][y][z + 1], dp[0][x][node][z + 1] + dp[0][node][y][z + 1] );
                        }
                    }
                }
            }
        }
    }

    int q;
    cin >> q;

    for(int i = 0; i < q; ++i)
    {
        int a, b, k, t;
        cin >> a >> b >> k >> t;
        --a; --b;
        int ans = dp[t][a][b][k];
        cout << ( ans != inf ? ans : -1 ) << '\n';
    }

    return 0;
}