 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert
 
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
set<ll> solve(vl A) {
    int N = sz(A);
    set<ll> res;
    F0R(m, 1 << N) {
        ll cur = 0;
        F0R(i, N) {
            if (m & (1 << i)) {
                cur += A[i];
            }
        }
        res.ins(cur);
    }
    return res;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);    
	
    int N; cin >> N; ll T; cin>>T;
    ll A[N]; F0R(i, N) cin >> A[i];
    int bp = N/2;
    vl B, C;
    F0R(i, N/2) B.pb(A[i]);
    FOR(i, N/2, N) C.pb(A[i]);
    set<ll> X = solve(B), Y = solve(C);
    ll ans = T;
    trav(a, X) {
        auto it = Y.ub(T-a);
        if (it == Y.begin()) continue;
        it--;
        ckmin(ans, T - a - *it);
    }
    cout << T-ans << nl;
	return 0;
}
 
#include <bits/stdc++.h>

using namespace std;

#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
using tp = tuple<ll, ll, ll>;

constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
//constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;

using Array = vector<ll>;
using Matrix = vector<Array>;

/*
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
*/

template<class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
    ll to, cap, rev;

    Edge(ll _to, ll _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
    G[from].push_back(Edge(to, cap, (ll) G[to].size()));
    if (revFlag)
        G[to].push_back(Edge(from, revCap, (ll) G[from].size() - 1));
}


void solve() {
    ll n;
    cin >> n;
    vec<ll> a(n - 1), b(n - 1);
    Graph g(n);
    REP(i, n - 1) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        add_edge(g, a[i], b[i], 1, true, 1);
    }

    vec<ll> d(n, 0);
    auto dfs = [&](auto &&self, ll v, ll p)->void {
        for (auto e:g[v]) {
            if (e.to == p) continue;
            d[e.to] = d[v] + 1;
            self(self,e.to,v);
        }
    };
    dfs(dfs, 0, -1);

    ll q;
    cin >> q;
    vec<ll> dp(n, 0);
    ll sum = 0;
    while (q--) {
        ll t, e, x;
        cin >> t >> e >> x;
        e--;
        if (t == 1) {
            if (d[a[e]] < d[b[e]]) {
                dp[b[e]] -= x;
                sum += x;
            } else {
                dp[a[e]] += x;
            }
        } else {
            if (d[b[e]] < d[a[e]]) {
                dp[a[e]] -= x;
                sum += x;
            } else {
                dp[b[e]] += x;
            }
        }
    }

    vec<ll> ans(n, 0);
    auto dfs2 = [&](auto &&self, int v, int p) -> void {
        ans[v] += dp[v];
        for (auto e:g[v]) {
            if (e.to == p) continue;
            dp[e.to] += dp[v];
            self(self, e.to, v);
        }
    };
    dp[0] += sum;
    dfs2(dfs2, 0, -1);
    REP(i, n) cout << dp[i] << en;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*
    ll t;
    cin >> t;
    REP(i, t - 1) {
        solve();
    }*/

    solve();

    return 0;
}
