// 2020-07-15 23:41:12
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = long long;
using ld = long double;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }

void answer() {
  using Work = tuple<int, int, int>; // (x, s, t)
  using P = pair<int, int>;
  int n, q;
  cin >> n >> q;
  vector<Work> works(n);
  rep(i, n) {
    int s, t, x;
    cin >> s >> t >> x;
    works[i] = { x, s-x, t-x };
  }
  sort(ALL(works));
  set<P> ds;
  rep(i, q) {
    int d;
    cin >> d;
    ds.emplace(d, i);
  }
  vector<int> ans(q, -1);
  for(const auto& w : works) {
    int x, s, t;
    tie(x, s, t) = w;
    auto it = ds.lower_bound({ s, -1 });
    while(it != ds.end() && (*it).first < t) {
      int d, qi;
      tie(d, qi) = *it;
      ans[qi] = x;
      it++;
      ds.erase(prev(it));
    }
  }
  for(const auto x : ans) cout << x << '\n';
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
const ll oo = 1e18;
const int MOD = 1000000007;
const int N = 300010;
#define x first
#define y second
#define pb push_back
#define mp make_pair

int n , m , dp[1 << 16][16], comp[1 << 16], cost[16][1 << 16], vis[1 << 16],val[1<<16], vsId;
struct edge {
	int s , t , c;
};
edge E[16 * 16];
int solve(int msk , int p){
	if(p == n-1)return !msk?0:-1e9;
	int &ret = dp[msk][p];
	if(ret != -1)return ret;
	ret = -1e9;
	for (int i = 0; i < n; ++i){
		if((msk&(1<<i))>0 && cost[i][1<<p]){
			ret = max(ret,cost[i][1<<p]+solve(msk^(1<<i),i));
		}
	}
	return ret;
}
ll all = 0;
vector<int> nodes;
int calc(int msk){
	if(!msk)return 0;
	if(vis[msk]==vsId)return val[msk];
	vis[msk] = vsId;
	int &ret = val[msk];
	ret = -1e9;
	for(int sub = msk ; sub > 0 ; sub=(sub-1)&msk){
		for(int u = 0 ; u < nodes.size() ; ++u){
			int j = nodes[u];
			ret = max(ret,cost[j][sub]+comp[sub]+calc(msk^sub));
		}
	}
	return ret;
}

int main() {
	memset(dp,-1,sizeof dp);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; ++i) {
		scanf("%d%d%d", &E[i].s, &E[i].t, &E[i].c);
		E[i].s--, E[i].t--;
		all += E[i].c;
	}
	for (int i = 0; i < n; ++i) {
		for (int msk = 0; msk < (1 << n); ++msk) {
			for (int j = 0 ; j < m ; ++j) {
				if (E[j].t == i)
					swap(E[j].s, E[j].t);
				if (E[j].s == i && (msk & (1 << E[j].t)) > 0) {
					cost[i][msk] += E[j].c;
				}
			}
		}
	}
	for (int msk = 0; msk < (1 << n); ++msk) {
		for (int j = 0 ; j < m ; ++j) {
			if((msk & (1 << E[j].s)) > 0 && (msk & (1 << E[j].t)) > 0){
				comp[msk] += E[j].c;
			}
		}
	}
	ll ans = oo;
	for (int msk = 0 ; msk < (1<< n); ++msk){
		if((msk&(1<<0))==0||(msk&(1<<(n-1)))==0)continue;
		if(solve(msk^(1<<0),0) < 0)continue;
		nodes.clear();
		vsId++;
		for(int i = 0 ; i < n ; ++i)
			if((msk&(1<<i))>0)nodes.pb(i);
		ans = min(ans,all-solve(msk^(1<<0),0)-calc(~msk&((1<<n)-1)));
	}
	printf("%lld\n",ans );
	return 0;
}
