#include"bits/stdc++.h"


#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define fr(x) freopen(x,"r",stdin)
#define fw(x) freopen(x,"w",stdout)
#define iout(x) printf("%d\n",x)
#define lout(x) printf("%lld\n",x)
#define REP(x,l,u) for(ll x = (l);x<=(u);x++)
#define RREP(x,l,u) for(ll x = (l);x>=(u);x--)
#define mst(x,a) memset(x,a,sizeof(x))
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define MP make_pair
#define se second
#define fi first
#define dbg(x) cout<<#x<<" = "<<(x)<<endl;
#define sz(x) ((int)x.size())
#define cl(x) x.clear()

typedef  long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ld;
using namespace std;

const int maxn = 100010;
const int mod = 1e9+7;
const int MAX = 1000000010;
const double eps = 1e-6;
const double PI = acos(-1);

template<typename T> inline void read(T &x){
x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;
}

template<typename A,typename B> inline void read(A&x,B&y){read(x);read(y);}
template<typename A,typename B,typename C> inline void read(A&x,B&y,C&z){read(x);read(y);read(z);}
template<typename A,typename B,typename C,typename D> inline void read(A&x,B&y,C&z,D&w){read(x);read(y);read(z);read(w);}
template<typename A,typename B> inline A fexp(A x,B p){A ans=1;for(;p;p>>=1,x=1LL*x*x%mod)if(p&1)ans=1LL*ans*x%mod;return ans;}
template<typename A,typename B> inline A fexp(A x,B p,A mo){A ans=1;for(;p;p>>=1,x=1LL*x*x%mo)if(p&1)ans=1LL*ans*x%mo;return ans;}

int n,m,TOT;

int G[16][16];

int f[(1<<15)+5][16];

int All[(1<<15)+5];

void Work(){
	REP(sta,0,(1<<n)-1)REP(i,1,n)f[sta][i]=-1000000000;f[1][1]=0;
	REP(sta,0,(1<<n)-1)
		REP(i,1,n)if((sta>>i-1)&1){
			REP(j,1,n)if(j!=i&&((sta>>j-1)&1)&&G[i][j])f[sta][i]=max(f[sta][i],f[sta^(1<<i-1)][j]+G[i][j]);
			for(int s=sta;s;s=(s-1)&sta)if(!((s>>i-1)&1))f[sta][i]=max(f[sta][i],f[sta^s][i]+All[s^(1<<i-1)]);
		}
	iout(TOT-f[(1<<n)-1][n]);
}

void Init(){
	read(n,m);
	REP(i,1,m){
		int u,v,w;
		read(u,v,w);
		G[u][v]=G[v][u]=w;
		TOT+=w;
	}
	REP(sta,0,(1<<n)-1){
		REP(i,1,n)if((sta>>i-1)&1)
			REP(j,i+1,n)if((sta>>j-1)&1)All[sta]+=G[i][j];
	}
}

int main(){
	Init();
	Work();
	return 0;
}

//  main.cpp
//  ABC174F2
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <tuple>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
// Binary Indexed Tree (Fenwick Tree)
//    使い方 :    BIT<int>bit
//                BIT<int> bt(n + 1); BITを初期化して
//                 bt.add(x, 1); xに1を加算
//                bt.sum(x); 0～xの累積和
template<typename T> // T: type of cost
struct BIT {
private:vector<T> array;
    const int n;
public:BIT(int _n):array(_n+1,0),n(_n) {}
    // iまでの累積和
    T sum(int i) {
        T x = 0;
        while(i>0){
            x += array[i];
            i-=i&-i; // LSBからの減算
        }
        return x;
    }
    // iからjの区間和
    T sum(int i,int j){
        T ret_i=sum(i-1);
        T ret_j=sum(j);
        return ret_j-ret_i;
    }
    // i番目にxを追加
    void add(int i, T x) {
        while(i<=n) {
            array[i] += x;
            i+=i&-i; // LSBへの加算
        }
    }
};

int main(int argc, const char * argv[]) {
    int n, q;
    cin >> n >> q;
    vector<int>c(n + 1);
    vector<int>p(n + 1, -1); // -1で初期化しておく
    vector<int> st(n + 1,0);
    // st(s)=t  左がsで右がtの矢印
    // ２回目の登場以降ならiをtとして登録
    for (int i = 1; i <= n; i++) {
        cin >> c.at(i);
        if (p.at(c.at(i)) != -1) {
            st.at(p.at(c.at(i)))=i;
        }
            p.at(c.at(i)) = i;
    }
    /*rep(i,n){
        cout<<i<<" "<<st.at(i)<<endl;
    }*/
    // クエリを整理する
    // q(l)=(r,i) q(左端)=(右端、読み込みの順番)
    int l, r;
    vector<int>len(q);
    vector<vector<P>> query(n+1,vector<P>()); // lの値によってクエリを整理する
    rep(i, q) {
        cin >> l >> r;
        query.at(l).emplace_back(r,i);
        len.at(i)=r-l+1;
    }
    /*for(int i=n-1;i>=0;i--){
        for(auto& x:query.at(i)){
            cout<<i<<" "<<x.first<<" "<<x.second<<endl;
        }
    }*/
 // BITを使う
    vector<int> cnt(q);
    BIT<int> bt(n + 1); // BITを初期化
    for (int s = n; s >= 1; s--) {
        if (st.at(s) > 0) {
            bt.add(st.at(s), 1);
        }
        for(auto& x:query.at(s)){
            cnt.at(x.second)=bt.sum(x.first);
        }
    }
    rep(i, q) {
        cout << len.at(i)-cnt.at(i) << endl;
    }
    return 0;
}
