openol I 60

#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
// Quick types
#define ll long long
#define ld long double
//#define ull unsigned long long
#define pii pair <int, int>
#define vi vector <int>
#define mi vector <vector <int>>
// Quick functions
#define endl "\n"
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define pb push_back
#define mp make_pair
// Quick fors
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORS(i, a, b, c) for (int i = a; i < b; i += c)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
#define EACH(e, a) for (auto& e : a)
// Pragmas
#ifndef TIOM4EG
#pragma GCC optimize("O3") // let the chaos begin!
#pragma GCC target("avx,avx2,tune=native")
#pragma GCC comment(linker, "/stack:200000000")
#endif
// PBDS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;
mt19937 rng(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());
//#define int long long
constexpr int INF = 1e9 + 7, MD = 998244353, MAX = 2007, LG = 18, R = 1 << LG, MOD = 1000000007, MOD2 = 1e9 + 9, B = 256;
const ll INFLL = 1e18 + 7;

struct state {
    ll v;
    int cl;
    char ml, mr;
    state() : v(-INFLL) {}
    state(ll a, int b, char c, char d) : v(a), cl(b), ml(c), mr(d) {}
};

void conv(vector <state>& c, const vector <state>& a, const vector <state>& b, char ml, char mr) {
    int i = 0, j = 0;
    if (a[0].v + b[0].v > c[0].v) c[0] = state(a[0].v + b[0].v, 0, ml, mr);
    FOR(k, 1, sz(a) + sz(b) - 1) {
        if (j == sz(b) - 1 || (i != sz(a) - 1 && a[i + 1].v + b[j].v > a[i].v + b[j + 1].v)) ++i;
        else ++j;
        if (a[i].v + b[j].v > c[k].v) c[k] = state(a[i].v + b[j].v, i, ml, mr);
    }
}

ll w[200007];
vector <state> dp[2 * R][4]; // dp[i][0] - whole, dp[i][1] - w/o first, dp[i][2] - w/o last, dp[i][3] - w/o first & last; 0 >= 1, 0 >= 2, 1 >= 3, 2 >= 3

void dac(int l, int r, int v = 1) {
    dp[v][0].resize(1 + (r - l + 1) / 2);
    dp[v][1].resize(1 + (r - l) / 2);
    dp[v][2].resize(1 + (r - l) / 2);
    dp[v][3].resize(1 + (r - l - 1) / 2);
    if (l + 1 == r) {
        dp[v][0][0] = state(0, 0, 0, 0);
        dp[v][0][1] = state(w[l], 1, 0, 0);
        dp[v][1][0] = state(0, 0, 0, 0);
        dp[v][2][0] = state(0, 0, 0, 0);
        dp[v][3][0] = state(0, 0, 0, 0);
        return;
    }
    int m = (l + r) / 2;
    dac(l, m, 2 * v), dac(m, r, 2 * v + 1);
    conv(dp[v][0], dp[2 * v][0], dp[2 * v + 1][1], 0, 1);
    conv(dp[v][0], dp[2 * v][2], dp[2 * v + 1][0], 2, 0);
    conv(dp[v][1], dp[2 * v][3], dp[2 * v + 1][0], 3, 0);
    conv(dp[v][1], dp[2 * v][1], dp[2 * v + 1][1], 1, 1);
    conv(dp[v][2], dp[2 * v][0], dp[2 * v + 1][3], 0, 3);
    conv(dp[v][2], dp[2 * v][2], dp[2 * v + 1][2], 2, 2);
    conv(dp[v][3], dp[2 * v][3], dp[2 * v + 1][2], 3, 2);
    conv(dp[v][3], dp[2 * v][1], dp[2 * v + 1][3], 1, 3);
}

vi ans;
void restore(int l, int r, int k, char c, int v = 1) {
    if (l + 1 == r) {
        ans.pb(l);
        return;
    }
    int m = (l + r) / 2;
    if (dp[v][c][k].cl) restore(l, m, dp[v][c][k].cl, dp[v][c][k].ml, 2 * v);
    if (k - dp[v][c][k].cl) restore(m, r, k - dp[v][c][k].cl, dp[v][c][k].mr, 2 * v + 1);
}

#define int long long

vi g[MAX];
int es[MAX], vw[MAX], ew[MAX], par[MAX], sub[MAX];
int dp2[2][MAX][MAX]; // took edge?, vertex, how many took
int tmp[2][MAX];

void dfs(int v, int p = -1) {
    sub[v] = 1;
    EACH(id, g[v]) {
        int u = es[id] - v;
        if (u == p) {
            par[v] = id;
            continue;
        }
        dfs(u, v);
        sub[v] += sub[u];
    }
    dp2[0][v][0] = 0;
    FOR(i, 0, sub[v]) tmp[0][i] = tmp[1][i] = -INFLL;
    EACH(id, g[v]) if (id != par[v]) {
        int u = es[id] - v;
        // not took v->u
        FOR(pr, 0, sub[u]) {
            RFOR(i, sub[v] - 1, pr + (pr & 1)) {
                tmp[0][i] = max(tmp[0][i], dp2[0][v][i - pr - (pr & 1)] + dp2[0][u][pr]);
                tmp[1][i] = max(tmp[1][i], dp2[1][v][i - pr - (pr & 1)] + dp2[0][u][pr]);
            }
        }
        // took v->u
        FORS(pr, 0, sub[u], 2) {
            RFOR(i, sub[v] - 1, pr + 1) {
                tmp[1][i] = max(tmp[1][i], dp2[0][u][pr] + max(dp2[0][v][i - pr - 1] + vw[v], dp2[1][v][i - pr - 1]) - ew[id]);
            }
        }
        FOR(i, 0, sub[v]) dp2[0][v][i] = max(dp2[0][v][i], tmp[0][i]), dp2[1][v][i] = max(dp2[1][v][i], tmp[1][i]);
    }
    FOR(i, 0, sub[v]) {
        if (i & 1) {
            if (~p) dp2[0][v][i] = max(dp2[0][v][i], dp2[1][v][i] - ew[par[v]]);
        }
        else dp2[0][v][i] = max(dp2[0][v][i], dp2[1][v][i]);
    }
}

#undef int

signed main() {
    FOR(i, 0, MAX) FOR(j, 0, MAX) dp2[0][i][j] = dp2[1][i][j] = -INFLL;
    fastIO;
    int n, k, t; cin >> n >> k >> t;
    if (n <= 2000) {
        FOR(i, 0, n) cin >> vw[i];
        FOR(i, 1, n) {
            int u, v; cin >> u >> v >> ew[i], --u, --v;
            es[i] = u + v;
            g[u].pb(i), g[v].pb(i);
        }
        dfs(0);
        cout << dp2[0][0][2 * k];
        return 0;
    }
    vi a(n); EACH(e, a) cin >> e;
    vi b(n - 1); FOR(i, 0, n - 1) cin >> b[i] >> b[i] >> b[i];
    FOR(i, 0, n - 2) w[i] = a[i + 1] - b[i] - b[i + 1];
    dac(0, n - 2, 1);
    cout << dp[1][0][k].v << endl;
    if (t) {
        restore(0, n - 2, k, 0, 1);
        EACH(e, ans) cout << e + 2 << ' ' << e + 1 << ' ' << e + 3 << endl;
    }
}