1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define BOOST ios_base::sync_with_stdio(0), cin.tie(0)
template<typename T>
using vc = vector<T>;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;

vc<vc<ii>> g;
int n;

int start = 0, mxdist = 0;
void far(int x, int p, int dist){
	if(dist > mxdist){
		start = x;
		mxdist = dist;
	}
	for(auto [y, d] : g[x]){
		if(y == p) continue;
		far(y, x, dist + d);
	}
}

vc<ll> t(3);
int ok = 0;
vc<int> on;
vc<vc<int>> path(3);

void dfs(int idx, int x, int p, ll left){
	on[x] = 1;
	path[idx].pb(x);
	if(left <= 0){
		if(idx == 2){
			ok = 1;
			return;
		}
		for(int i=0; i<=idx; i++){
			int s = (int)path[i].size();
			for(int j=0; j<s; j++){
				ll nl = t[idx+1];
				if(i == idx && j == s-1) nl += left;
				dfs(idx+1, path[i][j], 0, nl);
			}
		}
	}
	else{
		for(auto [y, d] : g[x]){
			if(y == p || on[y]) continue;
			dfs(idx, y, x, left - d);
		}
	}
		
	on[x] = 0;
	path[idx].pop_back();
}

void solve(){
	cin >> t[0] >> t[1] >> t[2];
	do{
		// cout << t[0] << " " << t[1] << " " << t[2] << "\n";
		// cout << t[0] << " " << t[
		ok = 0;
		on = vc<int>(n+1);
		path = vc<vc<int>>(3);
		dfs(0, start, 0, t[0]);
		if(ok){

			// for(int i=0; i<3; i++){
			// 	cout << "path " << i << ": ";
			// 	for(auto it : path[i]) cout << it << " ";
			// 	cout << "\n";
			// }

			cout << "TAK\n";
			return;
		}
	} while(next_permutation(t.begin(), t.end()));
	cout << "NIE\n";
}	

int main(){
	BOOST;
	int q;
	cin >> n >> q;
	g = vc<vc<ii>>(n+1);
	on = vc<int>(n+1);

	for(int i=0; i<n-1; i++){
		int a, b, c;
		cin >> a >> b >> c;
		g[a].pb({b, c});
		g[b].pb({a, c});
	}
	far(1, 0, 0);

	for(int i=0; i<q; i++){
		solve();
	}
}