Untitled

/// I am snatchin chains and burnin' tattoos
#include <bits/stdc++.h>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


using namespace std;

#define pb push_back
#define F first
#define S second
#define f(i, a, b) for (int i = a; i < b; i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(x) (int)(x).size()
#define mp(x, y) make_pair(x, y)
#define popCnt(x) (__builtin_popcountll(x))
#define int ll

using ll = long long;
using ii = pair<int, int>;
using ull = unsigned long long;

const int N = 1e6 + 5, A = 26 * 26, LG = 19, MOD = (119 << 23) + 1;
const long double PI = acos(-1);
const long double EPS = 1e-7;
vector<vector<int>> go[N];
int dp[205][205];
int cost[205][205], del[205];
int n, m;
int a[205];
int solve(int index, int prv) {
    if(index == n) return 0;
    int &ret = dp[index][prv];
    if(~ret)    return ret;
    ret = 1e17;
    if(a[index] >= prv) ret = min(ret, solve(index + 1, a[index]));
    ret = min(ret, solve(index + 1, prv) + del[a[index]]);
    f(i,1,201) if(i >= prv)ret = min(ret, solve(index+1,i)+cost[a[index]][i]);
    f(i,1,201) ret = min(ret, solve(index+1,prv)+cost[a[index]][i]+del[i]);
    return ret;
}
void doWork() {
    memset(dp,-1,sizeof dp);
    cin >> n >> m;
    f(i,0,n)    cin >> a[i];
    f(i,0,205)
        f(j,0,205) cost[i][j] = 1e17;
    f(i,0,205)cost[i][i] = 0, del[i]=1e17;
    f(i,0,m) {
        int tp;
        cin >> tp;
        if(tp == 1) {
            int x, y, c;
            cin >> x >> y >> c;
            cost[x][y] = min(cost[x][y], c);
        }   else {
            int x, c;
            cin >> x >> c;
            del[x] = min(del[x], c);
        }
    }
    f(k,0,205)
        f(i,0,205)
            f(j,0,205)cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
    int ans = solve(0,0);
    if(ans > 1e16) cout << "-1\n";
    else cout << ans << "\n";
}


int32_t main() {
#ifdef LOCAL
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif

    int t = 1;
    // cin >> t;
    while (t--) {
        doWork();
    }
}