#include <bits/stdc++.h> using namespace std; #define ff endl #define lf "\n" #define fi first #define se second #define _ << ' ' << #define all(x) begin(x),end(x) #define rall(x) rbegin(x),rend(x) #define infor(str, ...) do { fprintf(stderr, str, ##__VA_ARGS__); } while(0) #define infof(str, ...) do { fprintf(stderr, str"\n", ##__VA_ARGS__); } while(0) #ifndef DEBUG #undef infor #undef infof #define infor(str, ...) #define infof(str, ...) #endif using ll = long long; using pll = pair<ll, ll>; using pii = pair<int, int>; constexpr int LOG = 20; constexpr int MOD = 1e9+7; constexpr int MAXN = 6e5+7; int main(void) { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, K; cin >> N >> K; vector<pii> ed(2 * N); vector<int> W(2 * N), dg(2 * N); vector<vector<pii>> adj(2 * N); for(int i = 0; i < 2 * N; ++i) { auto &[u, v] = ed[i]; cin >> u >> v >> W[i]; u -= 1, v += N - 1; adj[u].emplace_back(v, i); adj[v].emplace_back(u, i); dg[u] += 1; dg[v] += 1; } queue<int> q; for(int i = 0; i < 2 * N; ++i) { if(dg[i] == 1) q.emplace(i); } while(!q.empty()) { auto v = q.front(); q.pop(); for(auto [u, w]: adj[v]) { dg[u] -= 1; if(dg[u] > 1) continue; q.emplace(u); } } for(int i = 0; i < 2 * N; ++i) { if(dg[i] <= 2) continue; cout << "NO" << lf; return 0; } vector<bool> vis(2 * N); auto dfs = [&](int v, int f, auto &&dfs) -> int { if(vis[v]) return 0; vis[v] = 1; infof("===== dfs(%d, %d) =====", v, f); infof("... dg[v] = %d", dg[v]); for(auto [u, w]: adj[v]) { if(w == f || dg[u] < 2) continue; return W[w] - dfs(u, w, dfs); } assert(0); }; vector<int> V; for(int i = 0; i < 2 * N; ++i) { if(dg[i] < 2) continue; int x = dfs(i, -1, dfs); if(x) V.emplace_back(abs(x)); } vector<array<bool, 2>> ok(2 * N); for(int i = 0; i < 2 * N; ++i) { if(!vis[i]) continue; int k = i >= N; for(auto [u, w]: adj[i]) { if(dg[u] == 2) continue; ok[w][k] = 1; if(vis[u]) continue; vis[u] = 1; q.emplace(u); } } while(!q.empty()) { auto v = q.front(); q.pop(); for(auto [u, w]: adj[v]) { if(dg[u] == 2) continue; ok[u][0] |= ok[v][1]; ok[u][1] |= ok[v][0]; if(vis[u]) continue; vis[u] = 1; q.emplace(u); } } int L = 0, R = 0; for(int i = 0; i < 2 * N; ++i) { auto [u, v] = ed[i]; auto w = W[i]; if(!vis[u] && !vis[v]) { V.emplace_back(v); continue; } if(ok[i][0] && ok[i][1]) { cout << "NO" << lf; return 0; } if(!ok[i][0] && !ok[i][1]) continue; if(ok[i][0]) { R += w; } else L += w; } int s = 0; bitset<MAXN> kp; kp[0] = 1; for(auto w: V) { s += w; kp |= kp << w; } int mn = INT_MAX; for(int i = 0; i <= s; ++i) { if(!kp[i]) continue; mn = min(mn, abs((L + i) - (R + s - i))); } if(mn <= K) { cout << "YES" << lf; } else cout << "NO" << lf; infof("mn = %d | K = %d", mn, K); }