#include <bits/stdc++.h>
using namespace std;
#define killua ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(0)
#define int long long
#define ll long long
ll mod = 1e9 + 9;
#define int long long
ll n,m;
int operation_less[201][201];
vector<ll>del(201,1e18);
int dp[201][201];
vector<ll>v(201);
int solve(ll idx,ll last)
{
if(idx==n)
return 0;
ll &ret=dp[idx][last];
if(ret!=-1)return ret;
ret=1e18;
for(int i=0;i<=200;i++)
{
if(operation_less[v[idx]][i]!=1e18)
{
if(i>=last)
ret=min(ret, solve(idx+1,i)+operation_less[v[idx]][i]);
ret=min(ret, solve(idx+1,last)+operation_less[v[idx]][i]+del[i]);
}
}
if(del[v[idx]]!=1e18)
ret=min(ret, solve(idx+1,last)+del[v[idx]]);
if(v[idx]>=last)ret=min(ret, solve(idx+1,v[idx]));
return ret;
}
signed main() {
killua;
cin>>n>>m;
for(int i=0;i<n;i++)
cin>>v[i];
for(int i=0;i<=200;i++)
{
for(int j=0;j<=200;j++)
operation_less[i][j]=1e18;
}
//vector<vector<pair<ll,ll>>>operation_less(n);
for(int i=0;i<m;i++)
{
ll op;
cin>>op;
if(op==1)
{
ll x,y,c;
cin>>x>>y>>c;
operation_less[x][y]=min(operation_less[x][y],c);
}
else
{
ll x,c;
cin>>x>>c;
del[x]=min(c,del[x]);
}
}
for(int i = 0 ; i <= 200 ;i++)operation_less[i][i] = 0;
for(int i = 0 ; i <= 200 ; i++)
{
for(int j = 0 ; j <= 200;j++)
{
for(int k = 0 ; k <= 200; k++)
{
operation_less[j][k] = min(operation_less[j][k] , operation_less[j][i] + operation_less[i][k]);
}
}
}
memset(dp,-1,sizeof dp);
if(solve(0,0)>=1e18)
cout<<-1<<endl;
else
cout<<solve(0,0)<<endl;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGtpbGx1YSBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKSwgY2luLnRpZShOVUxMKSwgY291dC50aWUoMCkKI2RlZmluZSBpbnQgbG9uZyBsb25nCiNkZWZpbmUgbGwgbG9uZyBsb25nCmxsIG1vZCA9IDFlOSArIDk7CiNkZWZpbmUgaW50IGxvbmcgbG9uZwpsbCBuLG07CmludCBvcGVyYXRpb25fbGVzc1syMDFdWzIwMV07CnZlY3RvcjxsbD5kZWwoMjAxLDFlMTgpOwppbnQgZHBbMjAxXVsyMDFdOwp2ZWN0b3I8bGw+digyMDEpOwppbnQgc29sdmUobGwgaWR4LGxsIGxhc3QpCnsKICAgIGlmKGlkeD09bikKICAgICAgICByZXR1cm4gMDsKICAgIGxsICZyZXQ9ZHBbaWR4XVtsYXN0XTsKICAgIGlmKHJldCE9LTEpcmV0dXJuIHJldDsKICAgIHJldD0xZTE4OwogICAgZm9yKGludCBpPTA7aTw9MjAwO2krKykKICAgIHsKICAgICAgICBpZihvcGVyYXRpb25fbGVzc1t2W2lkeF1dW2ldIT0xZTE4KQogICAgICAgIHsKICAgICAgICAgICAgaWYoaT49bGFzdCkKICAgICAgICAgICAgcmV0PW1pbihyZXQsIHNvbHZlKGlkeCsxLGkpK29wZXJhdGlvbl9sZXNzW3ZbaWR4XV1baV0pOwogICAgICAgICAgICByZXQ9bWluKHJldCwgc29sdmUoaWR4KzEsbGFzdCkrb3BlcmF0aW9uX2xlc3NbdltpZHhdXVtpXStkZWxbaV0pOwogICAgICAgIH0KICAgIH0KICAgIGlmKGRlbFt2W2lkeF1dIT0xZTE4KQogICAgICAgIHJldD1taW4ocmV0LCBzb2x2ZShpZHgrMSxsYXN0KStkZWxbdltpZHhdXSk7CiAgICBpZih2W2lkeF0+PWxhc3QpcmV0PW1pbihyZXQsIHNvbHZlKGlkeCsxLHZbaWR4XSkpOwogICAgcmV0dXJuIHJldDsKfQpzaWduZWQgbWFpbigpIHsKICAgIGtpbGx1YTsKCiAgICBjaW4+Pm4+Pm07CgogICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICBjaW4+PnZbaV07CiAgICBmb3IoaW50IGk9MDtpPD0yMDA7aSsrKQogICAgewogICAgICAgIGZvcihpbnQgaj0wO2o8PTIwMDtqKyspCiAgICAgICAgICAgIG9wZXJhdGlvbl9sZXNzW2ldW2pdPTFlMTg7CiAgICB9CgogICAgLy92ZWN0b3I8dmVjdG9yPHBhaXI8bGwsbGw+Pj5vcGVyYXRpb25fbGVzcyhuKTsKICAgIGZvcihpbnQgaT0wO2k8bTtpKyspCiAgICB7CiAgICAgICAgbGwgb3A7CiAgICAgICAgY2luPj5vcDsKICAgICAgICBpZihvcD09MSkKICAgICAgICB7CiAgICAgICAgICAgIGxsIHgseSxjOwogICAgICAgICAgICBjaW4+Png+Pnk+PmM7CiAgICAgICAgICAgIG9wZXJhdGlvbl9sZXNzW3hdW3ldPW1pbihvcGVyYXRpb25fbGVzc1t4XVt5XSxjKTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgbGwgeCxjOwogICAgICAgICAgICBjaW4+Png+PmM7CiAgICAgICAgICAgIGRlbFt4XT1taW4oYyxkZWxbeF0pOwogICAgICAgIH0KCiAgICB9CgogICAgZm9yKGludCBpID0gMCA7IGkgPD0gMjAwIDtpKyspb3BlcmF0aW9uX2xlc3NbaV1baV0gPSAwOwoKCiAgICBmb3IoaW50IGkgPSAwIDsgaSA8PSAyMDAgOyBpKyspCiAgICB7CiAgICAgICAgZm9yKGludCBqID0gMCA7IGogPD0gMjAwO2orKykKICAgICAgICB7CiAgICAgICAgICAgIGZvcihpbnQgayA9IDAgOyBrIDw9IDIwMDsgaysrKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBvcGVyYXRpb25fbGVzc1tqXVtrXSA9IG1pbihvcGVyYXRpb25fbGVzc1tqXVtrXSAsIG9wZXJhdGlvbl9sZXNzW2pdW2ldICsgb3BlcmF0aW9uX2xlc3NbaV1ba10pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgfQoKICAgIG1lbXNldChkcCwtMSxzaXplb2YgZHApOwogICAgaWYoc29sdmUoMCwwKT49MWUxOCkKICAgICAgICBjb3V0PDwtMTw8ZW5kbDsKICAgIGVsc2UKICAgICAgICBjb3V0PDxzb2x2ZSgwLDApPDxlbmRsOwoKfQ==