#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N;
#ifdef DEBUG
start:
	N=2+rand()%149;
	N=2;
#else
	cin>>N;
#endif
	int a[N+1],g[N+1][2];
	for(int i=1;i<=N;i++){
#ifdef DEBUG
		a[i]=rand()&1,g[i][0]=1+rand()%N,g[i][1]=1+rand()%N;
#else
		cin>>a[i]>>g[i][0]>>g[i][1];
#endif
	}
	int K;
#ifdef DEBUG
	K=N;
#else
	cin>>K;
#endif
	for(int _=0;_<1000;_++){
		vector<int>b(N-1);
		for(int i=0;i<N-1;i++){
			b[i]=rand()&1;
		}
		map<vector<int>,vector<int>>m;
		int ok=1;
		for(int z=1;z<=N;z++){
			vector<int>v(N-1),c(N*2);
			int x=z;
			for(int i=0;i<N-1;i++){
				v[i]=a[x];
				x=g[x][b[i]];
			}
			for(int i=0;i<N*2;i++){
				c[i]=a[x];
				x=g[x][a[x]];
			}
			if(m.count(v)&&m[v]!=c&&count(c.begin(),c.end(),0)&&count(c.begin(),c.end(),1)){
				// for(int i:v)cout<<i<<' ';cout<<endl;
				// for(int i:c)cout<<i<<' ';cout<<endl;
				// for(int i:m[v])cout<<i<<' ';cout<<endl;
				ok=0;
				break;
			}
			m[v]=c;
		}
		if(ok){
			vector<array<int,2>>t(1);
			vector<int>r(1);
			for(int z=1;z<=N;z++){
				vector<int>v(N-1);
				int x=z;
				int y=0;
				for(int i=0;i<N-1;i++){
					v[i]=a[x];
					if(t[y][a[x]]==0){
						t[y][a[x]]=t.size();
						t.emplace_back();
						r.push_back(-1);
					}
					r[y]=b[i];
					y=t[y][a[x]];
					x=g[x][b[i]];
				}
				if(r[y]!=-1){
					continue;
				}
				int xx=x;
				vector<int>c(N*2);
				for(int i=0;i<N*2;i++){
					c[i]=a[x];
					x=g[x][a[x]];
				}
				if(!count(c.begin(),c.end(),0)){
					r[y]=1;
					t[y][1]=y;
					continue;
				}
				if(!count(c.begin(),c.end(),1)){
					r[y]=0;
					t[y][0]=y;
					continue;
				}
				x=xx;
				vector<int>w(N+1);
				for(int i=0;i<N*2;i++){
					r[y]=a[x];
					if(w[g[x][a[x]]]){
						t[y][a[x]]=w[g[x][a[x]]];
						break;
					}
					w[x]=y;
					t[y][a[x]]=t.size();
					t.emplace_back();
					r.push_back(-1);
					y=t[y][a[x]];
					x=g[x][a[x]];
				}
				if(r[y]==-1){
					return 1;
				}
			}
			if(r.size()!=t.size()||count(r.begin(),r.end(),0)+count(r.begin(),r.end(),1)!=r.size()){
				return 1;
			}
			if(t.size()>50000){
				return 1;
			}
			for(int z=1;z<=N;z++){
				int x=z,y=0;
				int k=0;
				for(int i=0;i<100000;i++){
					k+=r[y]!=a[x];
					int xx=g[x][r[y]];
					int yy=t[y][a[x]];
					x=xx;
					y=yy;
				}
				if(k>=K){ /* HAS TO BE LESS!!! */
					cout<<z<<' '<<k<<'\n';
					return 1;
				}
			}
#ifdef DEBUG
			cout<<"OK"<<endl;
			goto start;
#else
			cout<<t.size()<<' '<<1<<'\n';
			for(int i=0;i<t.size();i++){
				cout<<r[i]<<' '<<t[i][0]+1<<' '<<t[i][1]+1<<'\n';
			}
#endif
			return 0;
		}
	}
#ifdef DEBUG
	cout<<N<<endl;
	for(int i=1;i<=N;i++){
		cout<<a[i]<<' '<<g[i][0]<<' '<<g[i][1]<<endl;
	}
#endif
	return 1;
}