#include <bits/stdc++.h>
#define err(args...) {}
#ifdef DEBUG
#include "_debug.cpp"
#endif
using namespace std;
using ll = long long;
using ld = long double;
template <typename T> using lim = numeric_limits<T>;
template <typename T> istream& operator>>(istream& is, vector<T>& a) { for(T& x : a) { is >> x; } return is; }
template <typename X, typename Y> istream& operator>>(istream& is, pair<X, Y>& p) { return is >> p.first >> p.second; }
enum class event_t { start, end, query };
struct event {
    event_t type;
    int pos, val;
};
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<event> events;
    for(int i = 0; i < n; i++) {
        int s, t, x;
        cin >> s >> t >> x;
        events.push_back({event_t::start, s - x, x});
        events.push_back({event_t::end, t - x, x});
    }
    for(int i = 0; i < q; i++) {
        int d;
        cin >> d;
        events.push_back({event_t::query, d, i});
    }
    vector<int> ans(q);
    sort(events.begin(), events.end(), [](auto& e1, auto& e2) {
        return pair{e1.pos, e1.type} < pair{e2.pos, e2.type};
    });
    multiset<int> s;
    for(auto& e : events) {
        if(e.type == event_t::start) {
            s.insert(e.val);
        } else if(e.type == event_t::end) {
            s.erase(s.find(e.val));
        } else {
            ans[e.val] = s.empty() ? -1 : *s.begin();
        }
    }
    for(int i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
using namespace std;
typedef long long LL;
const int N = 15;
const int MAXS = (1 << N) + 5;

template <typename T> inline void read(T &AKNOI) {
    T x = 0, flag = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') flag = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    AKNOI = flag * x;
}

template <typename T> inline void cmax(T &x, T y) {
	if (x < y) x = y;
}

int n, m, S, g[N][N], bin[N], id[MAXS];
int sum[MAXS], dp[MAXS][N];

void init() {
	read(n); read(m);
	S = (1 << n);
	for (int i = 0; i < n; ++i) {
		bin[i] = (1 << i);
		id[bin[i]] = i;
	}
	for (int i = 1; i <= m; ++i) {
		int a, b, c;
		read(a); read(b); read(c);
		g[a - 1][b - 1] = g[b - 1][a - 1] = c;
	}
	for (int s = 1; s < S; ++s) {
		int u = id[s & (-s)];
		sum[s] = sum[s ^ bin[u]];
		for (int i = u + 1; i < n; ++i) {
			if ((s >> i) & 1) {
				sum[s] += g[u][i];
			}
		}
	}
}

void solve() {
	mset(dp, 0x80);
	int ans = dp[0][0];
	dp[1][0] = 0;
	for (int s = 1; s < S; ++s) {
		for (int i = 0; i < n; ++i) {
			for (int t = s; t; t = (t - 1) & s) {
				if (t & bin[i]) {
					cmax(dp[s][i], dp[s ^ t ^ bin[i]][i] + sum[t]);
				}
			}
			for (int j = 0; j < n; ++j) {
				if ((s >> j) & 1) continue;
				if (!g[i][j]) continue;
				cmax(dp[s | bin[j]][j], dp[s][i] + g[i][j]);
			}
		}
		if (s & bin[n - 1]) {
			cmax(ans, dp[s][n - 1]);
		}
	}
	printf("%d\n", sum[S - 1] - ans);
}

int main() {
	init();
	solve();
	return 0;
}
