Chef _c8kbf_ has an unrooted, weighted tree with N nodes, where vertices u and v are connected by an edge with weight w.

The value of the simple path from x to y is defined as the [bitwise XOR] of the weights of the edges it consists of.  
Recall that a simple path is a path that does not have repeating vertices.

Help Chef _c8kbf_ find any four vertices a, b, c, d, such that:
a < b and c < d;
The value of the simple path from a to b is equal to that of the path from c to d;
The pairs (a, b) and (c, d) are different. In other words, a \neq c or b \neq d.  
Note that the four vertices do not have to be all distinct. For example, it is allowed for a and c to be the same if b and d are different.

If no four vertices satisfy such a property, report so. If there are multiple answers, output any one of them.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of multiple lines of input. For each test case,
- The first line contains an integer N, the number of vertices.
- The next N-1 lines contain three space-separated integers u_{i}, v_{i}, and w_{i}, denoting an edge between u_{i} and v_{i} with weight w_{i}. It is guaranteed that these edges will form a tree.

------ Output Format ------ 

For each test case, output four space-separated integers a, b, c, and d on a new line, representing the four vertices. If there are multiple answers, output any one of them.

If no four vertices satisfy the property, output -1 on a new line instead.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$3 ≤ N ≤ 10^{5}$
$1 ≤ u_{i}, v_{i} ≤ N$
$u_{i} \neq v_{i}$ for each $1 ≤ i ≤ N-1$.
$0 ≤ w_{i} ≤ 2^{20}$
- It is guaranteed that the given edges will form a tree.
- The sum of $N$ over all test cases won't exceed $3\cdot10^{5}$.

----- Sample Input 1 ------ 
3
4
1 2 1
2 3 2
2 4 3
4
1 2 2
2 3 4
2 4 8
3
1 2 5
2 3 0
----- Sample Output 1 ------ 
1 4 2 3
-1
1 2 1 3
----- explanation 1 ------ 
Test case $1$: The _value_ of the path between vertices $1$ and $4$ is $1\oplus 3 = 2$. The path between vertices $3$ and $2$ only has one edge, so the _value_ is also $2$. Note that $2$ $3$ $1$ $4$ or $2$ $4$ $1$ $3$ would be other acceptable answers.

Test case $2$: No four vertices satisfy the property.

Test case $3$: Note that $a = c$ for the output of this case, which is allowed.

Source: codechef | Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Tree algorithms

Mathematics

Data structures


Solutions:
t = int(input())
ans = []
for _ in range(t):
	n = int(input())
	l = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		l[u].append([v, w])
		l[v].append([u, w])
	xorl = [0 for i in range(n + 1)]
	visited = [False for i in range(n + 1)]
	queue = [l[1]]
	q2 = [1]
	visited[1] = True
	while queue:
		s = queue.pop(0)
		si = q2.pop(0)
		for i in s:
			if visited[i[0]] == False:
				xorl[i[0]] = xorl[si] ^ i[1]
				queue.append(l[i[0]])
				q2.append(i[0])
				visited[i[0]] = True
	d = {}
	t = 0
	for i in range(1, len(xorl)):
		for j in range(i + 1, len(xorl)):
			if xorl[i] ^ xorl[j] in d:
				a = d[xorl[i] ^ xorl[j]][0]
				b = d[xorl[i] ^ xorl[j]][1]
				c1 = i
				d1 = j
				t = 1
			else:
				d[xorl[i] ^ xorl[j]] = [i, j]
		if t:
			break
	if t:
		print(a, b, c1, d1)
	else:
		print(-1)


import math
import bisect
for _ in range(int(input())):
	n = int(input())
	l = [[] for i in range(n + 1)]
	for i in range(n - 1):
		a = list(map(int, input().strip().split()))
		l[a[0]].append([a[1], a[2]])
		l[a[1]].append([a[0], a[2]])
	xorl = [0] * (n + 1)
	visited = [False] * (n + 1)
	queue = []
	q2 = []
	q2.append(1)
	queue.append(l[1])
	visited[1] = True
	while queue:
		s = queue.pop(0)
		si = q2.pop(0)
		for i in s:
			if visited[i[0]] == False:
				xorl[i[0]] = xorl[si] ^ i[1]
				queue.append(l[i[0]])
				q2.append(i[0])
				visited[i[0]] = True
	d = {}
	t = 0
	for i in range(1, len(xorl)):
		for j in range(i + 1, len(xorl)):
			if xorl[i] ^ xorl[j] in d:
				a1 = d[xorl[i] ^ xorl[j]][0]
				b1 = d[xorl[i] ^ xorl[j]][1]
				c1 = i
				d1 = j
				t = 1
				break
			else:
				d[xorl[i] ^ xorl[j]] = [i, j]
		if t:
			break
	if t:
		print(a1, b1, c1, d1)
	else:
		print(-1)


mod_ = 10 ** 9 + 7
ans = [[-1]]

def dfs(root, g, p, px, weight, start, map_):
	xor = px ^ weight
	(left, right) = (min(start, root), max(start, root))
	if start != root and xor in map_:
		if map_[xor] != (left, right):
			ans[0] = [*map_[xor], left, right]
			return
	map_[xor] = (left, right)
	for (v, w) in g[root]:
		if len(ans[0]) == 4:
			return
		if v == p:
			continue
		dfs(v, g, root, xor, w, start, map_)
t = int(input())
for _ in range(t):
	ans[0] = [-1]
	n = int(input())
	g = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		g[u].append([v, w])
		g[v].append([u, w])
	map_ = {}
	for i in range(1, n + 1):
		if len(ans[0]) == 4:
			break
		dfs(i, g, 0, 0, 0, i, map_)
	print(*ans[0])


def solve2(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			solve2(adj, x[0], vis, dis)

def solve():
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	(dist, vis) = ([0] * n, [0] * n)
	dist[0] = 0
	solve2(adj, 0, vis, dist)
	mp = {}
	for i in range(n):
		if dist[i] in mp:
			mp[dist[i]].append(i)
		else:
			mp[dist[i]] = [i]
	for x in mp.items():
		if len(x[1]) > 1:
			(f, s) = (x[1][0], x[1][1])
			if f == 0 and s == n - 1:
				print('1 2 2', n - 1)
			elif f == 0:
				print('1', n - 1, s + 1, n - 1)
			elif s == n - 1:
				print('1', f + 1, '1', s + 1)
			else:
				print('1', f + 1, '1', s + 1)
			return
	mp2 = {}
	for i in range(n):
		for j in range(i + 1, n):
			if dist[i] ^ dist[j] in mp2:
				mp2[dist[i] ^ dist[j]].append([i, j])
			else:
				mp2[dist[i] ^ dist[j]] = [[i, j]]
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print('-1')
t = int(input())
for i in range(t):
	solve()


import sys
input = sys.stdin.readline

def dfs(dist, graph, node=1):
	for child in graph[node]:
		if dist[child[0]] == -1:
			dist[child[0]] = dist[node] ^ child[1]
			dfs(dist, graph, child[0])

def solve():
	n = int(input())
	graph = {}
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		if u in graph:
			graph[u].append((v, w))
		else:
			graph[u] = [(v, w)]
		if v in graph:
			graph[v].append((u, w))
		else:
			graph[v] = [(u, w)]
	distances = [-1] * (n + 1)
	distances[0] = 0
	distances[1] = 0
	dfs(distances, graph)
	m = {}
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			currDistance = distances[i] ^ distances[j]
			if currDistance not in m:
				m[currDistance] = (i, j)
			else:
				(a, b) = m[currDistance]
				print(a, b, i, j)
				return
	print(-1)
	return
for _ in range(int(input())):
	solve()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	graph = defaultdict(list)
	for __ in range(n - 1):
		(u, v, w) = map(int, input().split())
		graph[u].append([v, w])
		graph[v].append([u, w])
	dp = [0 for i in range(n + 1)]

	def dfs(graph, src, dp, par=-1):
		for (child, wt) in graph[src]:
			if child != par:
				dp[child] = dp[src] ^ wt
				dfs(graph, child, dp, src)
	dfs(graph, 1, dp)
	f = 0
	res = {}
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			val = dp[i] ^ dp[j]
			if val in res:
				print(str(res[val][0]) + ' ' + str(res[val][1]) + ' ' + str(i) + ' ' + str(j))
				f = 1
				break
			else:
				res[val] = (i, j)
		if f:
			break
	if not f:
		print(-1)


from collections import *
from math import *
from queue import *
from heapq import *
t_ = int(input())
for _ in range(t_):
	n = int(input())
	adj = defaultdict(list)
	for __ in range(n - 1):
		(u, v, wt) = map(int, input().split())
		adj[u].append([v, wt])
		adj[v].append([u, wt])
	prefixXor = [0] * (n + 1)

	def dfs(adj, src, prefixXor, par):
		for (neigh, wt) in adj[src]:
			if neigh != par:
				prefixXor[neigh] = prefixXor[src] ^ wt
				dfs(adj, neigh, prefixXor, src)
	dfs(adj, 1, prefixXor, -1)
	res = {}

	def solve():
		for k1 in range(1, len(prefixXor)):
			v1 = prefixXor[k1]
			for k2 in range(k1 + 1, len(prefixXor)):
				v2 = prefixXor[k2]
				tmp = v1 ^ v2
				if tmp in res:
					if res[tmp][0] != k1 or res[tmp][0] != k2:
						return (res[tmp][0], res[tmp][1], k1, k2)
				res[v1 ^ v2] = (k1, k2)
		return (-1,)
	print(*solve())


from collections import defaultdict

def solve(curr, xor):
	if visited[curr - 1]:
		cache[curr] = xor
		visited[curr - 1] = 0
		for (av, w) in tree[curr]:
			if visited[av - 1]:
				solve(av, xor ^ w)
t = int(input())
for _ in range(0, t):
	tree = defaultdict(list)
	n = int(input())
	cache = defaultdict(list)
	for i in range(1, n):
		(u, v, w) = map(int, input().split())
		tree[u].append([v, w])
		tree[v].append([u, w])
		cache[w].append([u, v])
	visited = [1] * n
	solve(1, 0)
	store = {}
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			xor = cache[i] ^ cache[j]
			if xor in store:
				print(*[store[xor][0], store[xor][1], i, j])
				break
			else:
				store[xor] = [i, j]
		else:
			continue
		break
	else:
		print(-1)
	continue


def fn(weight, tree, travelled, graph):
	travelled[tree] = 1
	for val in weight[tree]:
		if not travelled[val[0]]:
			graph[val[0]] = graph[tree] ^ val[1]
			fn(weight, val[0], travelled, graph)

def solve():
	n = int(input())
	weight = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		weight[u].append([v, w])
		weight[v].append([u, w])
	number = [0] * n
	travelled = [0] * n
	number[0] = 0
	fn(weight, 0, travelled, number)
	mp = {}
	for i in range(n):
		if number[i] in mp:
			mp[number[i]].append(i)
		else:
			mp[number[i]] = [i]
	for val in mp.items():
		if len(val[1]) > 1:
			f = val[1][0]
			s = val[1][1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	flag = {}
	for i in range(n):
		for j in range(i + 1, n):
			if number[i] ^ number[j] in flag:
				flag[number[i] ^ number[j]].append([i, j])
				if len(flag[number[i] ^ number[j]]) > 1:
					print(flag[number[i] ^ number[j]][0][0] + 1, flag[number[i] ^ number[j]][0][1] + 1, flag[number[i] ^ number[j]][1][0] + 1, flag[number[i] ^ number[j]][1][1] + 1)
					return
			else:
				flag[number[i] ^ number[j]] = [[i, j]]
	print(-1)
t = int(input())
for _ in range(t):
	solve()


import sys
import copy
import math
import heapq
import bisect
import statistics
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from heapq import heapify, heappush, heappop
from itertools import permutations, combinations
from collections import Counter, OrderedDict, deque
from bisect import bisect_left as bl, bisect_right as br
from functools import lru_cache, reduce
sys.setrecursionlimit(100000000)
inp = lambda : int(input())
strr = lambda : input().strip()
jl = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
muli = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
mod = 1000000007

def xd(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			xd(adj, x[0], vis, dis)

def xd1(adj, node, v, d):
	v[node] = 0
	for x in adj[node]:
		if not v[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			xd1(adj, x[0], v, dis)
for _ in range(int(input())):
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(a, b, w) = map(int, input().split())
		a = a - 1
		b = b - 1
		adj[a].append([b, w])
		adj[b].append([a, w])
	dist = [0] * n
	vis = [0] * n
	k = float('inf')
	m = [0] * n
	i = [0] * n
	dist[0] = 0
	xd(adj, 0, vis, dist)
	mp = {}
	h = 0
	for i in range(n):
		if dist[i] not in mp:
			mp[dist[i]] = []
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			(f, s) = (x[1][0], x[1][1])
			if f == 0 and s == n - 1:
				h = 2
				print('1 2 2 ' + str(n - 1))
			elif f == 0:
				h = 2
				print('1 ' + str(n - 1) + ' ' + str(s + 1) + ' ' + str(n - 1))
			elif s == n - 1:
				h = 2
				print('1 ' + str(f + 1) + ' 1 ' + str(s + 1))
			else:
				h = 2
				print('1 ' + str(f + 1) + ' 1 ' + str(s + 1))
			break
	else:
		mp2 = {}
		for i in range(n):
			for j in range(i + 1, n):
				if dist[i] ^ dist[j] not in mp2:
					mp2[dist[i] ^ dist[j]] = []
				mp2[dist[i] ^ dist[j]].append([i, j])
				if len(mp2[dist[i] ^ dist[j]]) > 1:
					print(str(mp2[dist[i] ^ dist[j]][0][0] + 1) + ' ' + str(mp2[dist[i] ^ dist[j]][0][1] + 1) + ' ' + str(mp2[dist[i] ^ dist[j]][1][0] + 1) + ' ' + str(mp2[dist[i] ^ dist[j]][1][1] + 1))
					h = 1
					break
			if h == 1:
				break
	if h == 0:
		print('-1')


import sys
sys.setrecursionlimit(100000)

def fn(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			fn(adj, x[0], vis, dis)

def solve():
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * n
	vis = [0] * n
	dist[0] = 0
	fn(adj, 0, vis, dist)
	mp = {}
	for i in range(n):
		if dist[i] in mp:
			mp[dist[i]].append(i)
		else:
			mp[dist[i]] = [i]
	for x in mp.items():
		if len(x[1]) > 1:
			(f, s) = (x[1][0], x[1][1])
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	mp2 = {}
	for i in range(n):
		for j in range(i + 1, n):
			if dist[i] ^ dist[j] in mp2:
				mp2[dist[i] ^ dist[j]].append([i, j])
				if len(mp2[dist[i] ^ dist[j]]) > 1:
					gg1 = mp2[dist[i] ^ dist[j]][0][0] + 1
					gg2 = mp2[dist[i] ^ dist[j]][0][1] + 1
					gg3 = mp2[dist[i] ^ dist[j]][1][0] + 1
					gg4 = mp2[dist[i] ^ dist[j]][1][1] + 1
					print(gg1, gg2, gg3, gg4)
					return
			else:
				mp2[dist[i] ^ dist[j]] = [[i, j]]
	print(-1)
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict

def df(ad, node, dst, vised):
	vised[node] = True
	for (i, j) in ad[node]:
		if not vised[i]:
			dst[i] = dst[node] ^ j
			df(ad, i, dst, vised)

def sol():
	ad = defaultdict(list)
	n = int(input())
	for L in range(n - 1):
		(x, v, w) = map(int, input().split())
		ad[x - 1].append([v - 1, w])
		ad[v - 1].append([x - 1, w])
	dst = [float('inf')] * n
	vised = [False] * n
	dst[0] = 0
	df(ad, 0, dst, vised)
	hash = defaultdict(list)
	for i in range(n):
		hash[dst[i]].append(i)
	for (k, nodes) in hash.items():
		if len(nodes) > 1:
			(x, v) = (nodes[0], nodes[1])
			if x == 0 and v == n - 1:
				print(1, 2, 2, n - 1)
			elif x == 0:
				print(1, n - 1, v + 1, n - 1)
			elif v == n - 1:
				print(1, x + 1, 1, v + 1)
			else:
				print(1, x + 1, 1, v + 1)
			return
	hash1 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			hash1[dst[i] ^ dst[j]].append([i, j])
			if len(hash1[dst[i] ^ dst[j]]) > 1:
				print(hash1[dst[i] ^ dst[j]][0][0] + 1, hash1[dst[i] ^ dst[j]][0][1] + 1, hash1[dst[i] ^ dst[j]][1][0] + 1, hash1[dst[i] ^ dst[j]][1][1] + 1)
				return
	print(-1)
	return
te = int(input())
while te:
	te -= 1
	sol()


def fnxor(ad, node, vi, dis):
	vi[node] = 1
	for xx in ad[node]:
		if not vi[xx[0]]:
			dis[xx[0]] = dis[node] ^ xx[1]
			fnxor(ad, xx[0], vi, dis)

def solve():
	n = int(input())
	ad = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		ad[u].append([v, w])
		ad[v].append([u, w])
	dis = [0] * n
	vi = [0] * n
	dis[0] = 0
	fnxor(ad, 0, vi, dis)
	mp = {}
	for i in range(n):
		if dis[i] in mp:
			mp[dis[i]].append(i)
		else:
			mp[dis[i]] = [i]
	for xx in mp.items():
		if len(xx[1]) > 1:
			ff = xx[1][0]
			ss = xx[1][1]
			if ff == 0:
				print('1', n - 1, ss + 1, n - 1)
			elif ff == 0 and ss == n - 1:
				print('1', '2', '2', n - 1)
			elif ss == n - 1:
				print('1', ff + 1, '1', ss + 1)
			else:
				print('1', ff + 1, '1', ss + 1)
			return
	Map2 = {}
	for i in range(n):
		for j in range(i + 1, n):
			if dis[i] ^ dis[j] in Map2:
				Map2[dis[i] ^ dis[j]].append([i, j])
				if len(Map2[dis[i] ^ dis[j]]) > 1:
					print(Map2[dis[i] ^ dis[j]][0][0] + 1, Map2[dis[i] ^ dis[j]][0][1] + 1, Map2[dis[i] ^ dis[j]][1][0] + 1, Map2[dis[i] ^ dis[j]][1][1] + 1)
					return
			else:
				Map2[dis[i] ^ dis[j]] = [[i, j]]
	print('-1')
t = int(input())
for _ in range(t):
	solve()


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def dfs(l, j, v, d):
	v[j] = 1
	for x in l[j]:
		if v[x[0]] == 0:
			d[x[0]] = d[j] ^ x[1]
			dfs(l, x[0], v, d)
t = inp()
for i in range(t):
	n = inp()
	l = [[] for _ in range(0, n)]
	for i in range(n - 1):
		(a, b, c) = mp()
		a = a - 1
		b = b - 1
		l[a].append((b, c))
		l[b].append((a, c))
	dst = [0] * n
	v = [0] * n
	dfs(l, 0, v, dst)
	d = {}
	for i in range(n):
		try:
			d[i].append(i)
		except:
			d[i] = [i]
	f = 0
	if f == 0:
		d2 = {}
		for i in range(n):
			for j in range(i + 1, n):
				try:
					d2[dst[i] ^ dst[j]].append((i, j))
				except:
					d2[dst[i] ^ dst[j]] = [(i, j)]
				if len(d2[dst[i] ^ dst[j]]) > 1:
					print(d2[dst[i] ^ dst[j]][0][0] + 1, d2[dst[i] ^ dst[j]][0][1] + 1, d2[dst[i] ^ dst[j]][1][0] + 1, d2[dst[i] ^ dst[j]][1][1] + 1)
					f = 2
					break
			if f == 2:
				break
	if f == 0:
		print(-1)


from collections import defaultdict

def get2(x, node, visit, distance):
	visit[node] = 1
	for i in x[node]:
		if not visit[i[0]]:
			distance[i[0]] = distance[node] ^ i[1]
			get2(x, i[0], visit, distance)

def get():
	n = int(input())
	x = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		x[u].append([v, w])
		x[v].append([u, w])
	distance = [0] * n
	visit = [0] * n
	distance[0] = 0
	get2(x, 0, visit, distance)
	dic = defaultdict(list)
	for i in range(n):
		dic[distance[i]].append(i)
	for i in dic.items():
		if len(i[1]) > 1:
			f = i[1][0]
			s = i[1][1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	dic2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			dic2[distance[i] ^ distance[j]].append([i, j])
			if len(dic2[distance[i] ^ distance[j]]) > 1:
				print(dic2[distance[i] ^ distance[j]][0][0] + 1, dic2[distance[i] ^ distance[j]][0][1] + 1, dic2[distance[i] ^ distance[j]][1][0] + 1, dic2[distance[i] ^ distance[j]][1][1] + 1)
				return
	print(-1)
for _ in range(int(input())):
	get()


import math
import bisect
for _ in range(int(input())):
	n = int(input())
	l = [[] for i in range(n + 1)]
	for i in range(n - 1):
		a = list(map(int, input().strip().split()))
		l[a[0]].append([a[1], a[2]])
		l[a[1]].append([a[0], a[2]])
	if n <= 500:
		xorl = [0] * (n + 1)
		visited = [False] * (n + 1)
		queue = []
		q2 = []
		q2.append(1)
		queue.append(l[1])
		visited[1] = True
		while queue:
			s = queue.pop(0)
			si = q2.pop(0)
			for i in s:
				if visited[i[0]] == False:
					xorl[i[0]] = xorl[si] ^ i[1]
					queue.append(l[i[0]])
					q2.append(i[0])
					visited[i[0]] = True
		d = {}
		t = 0
		for i in range(1, len(xorl)):
			for j in range(i + 1, len(xorl)):
				if xorl[i] ^ xorl[j] in d:
					a1 = d[xorl[i] ^ xorl[j]][0]
					b1 = d[xorl[i] ^ xorl[j]][1]
					c1 = i
					d1 = j
					t = 1
					break
				else:
					d[xorl[i] ^ xorl[j]] = [i, j]
			if t:
				break
		if t:
			print(a1, b1, c1, d1)
		else:
			print(-1)
	elif n <= 20000:
		t = 0
		for k in range(1, n):
			xorl = [0] * (n + 1)
			visited = [False] * (n + 1)
			queue = []
			q2 = []
			q2.append(k)
			queue.append(l[k])
			visited[k] = True
			while queue:
				s = queue.pop(0)
				si = q2.pop(0)
				for i in s:
					if visited[i[0]] == False:
						xorl[i[0]] = xorl[si] ^ i[1]
						queue.append(l[i[0]])
						q2.append(i[0])
						visited[i[0]] = True
			d = {}
			for i in range(1, len(xorl)):
				if i != k:
					if xorl[i] in d:
						b1 = d[xorl[i]]
						d1 = i
						a1 = k
						c1 = k
						t = 1
						break
					else:
						d[xorl[i]] = i
			if len(d) == len(xorl) - 2:
				for i in range(1, len(l)):
					for j in range(len(l[i])):
						if l[i][j][1] in d:
							a1 = k
							b1 = d[l[i][j][1]]
							c1 = i
							d1 = l[i][j][0]
							if a1 == c1 and b1 == d1 or (a1 == d1 and b1 == c1):
								pass
							else:
								t = 1
								break
					if t == 1:
						break
			if t == 1:
				break
		if t == 1:
			print(a1, b1, c1, d1)
		else:
			xorl = [0] * (n + 1)
			visited = [False] * (n + 1)
			queue = []
			q2 = []
			q2.append(1)
			queue.append(l[1])
			visited[1] = True
			while queue:
				s = queue.pop(0)
				si = q2.pop(0)
				for i in s:
					if visited[i[0]] == False:
						xorl[i[0]] = xorl[si] ^ i[1]
						queue.append(l[i[0]])
						q2.append(i[0])
						visited[i[0]] = True
			d = {}
			for i in range(2, len(xorl)):
				if xorl[i] in d:
					b1 = d[xorl[i]]
					d1 = i
					break
				else:
					d[xorl[i]] = i
			if len(d) == len(xorl) - 2:
				t = 0
				for i in range(2, len(xorl)):
					for j in range(i, len(xorl)):
						if i != j:
							y = xorl[i]
							z = xorl[j]
							if y ^ z in d:
								a1 = 1
								b1 = d[xorl[i] ^ xorl[j]]
								c1 = i
								d1 = j
								t = 1
								break
					if t == 1:
						break
				if t == 1:
					print(a1, b1, c1, d1)
				else:
					print(-1)
			else:
				print(1, b1, 1, d1)
	else:
		xorl = [0] * (n + 1)
		visited = [False] * (n + 1)
		queue = []
		q2 = []
		q2.append(1)
		queue.append(l[1])
		visited[1] = True
		while queue:
			s = queue.pop(0)
			si = q2.pop(0)
			for i in s:
				if visited[i[0]] == False:
					xorl[i[0]] = xorl[si] ^ i[1]
					queue.append(l[i[0]])
					q2.append(i[0])
					visited[i[0]] = True
		d = {}
		for i in range(2, len(xorl)):
			if xorl[i] in d:
				b1 = d[xorl[i]]
				d1 = i
				break
			else:
				d[xorl[i]] = i
		if len(d) == len(xorl) - 2:
			t = 0
			for i in range(len(l)):
				for j in range(len(l[i])):
					if l[i][j][1] in d:
						a1 = 1
						b1 = d[l[i][j][1]]
						c1 = i
						d1 = l[i][j][0]
						if a1 == c1 and b1 == d1 or (a1 == d1 and b1 == c1):
							pass
						elif a1 != b1 and c1 != d1:
							t = 1
							break
				if t == 1:
					break
			if t == 1:
				print(a1, b1, c1, d1)
			else:
				print(-1)
		else:
			print(1, b1, 1, d1)


def solve(node):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dist[x[0]] = dist[node] ^ x[1]
			solve(x[0])

def main():
	n = int(input())
	global adj
	adj = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	global vis
	global dist
	dist = [0] * n
	vis = [0] * n
	solve(0)
	mp = {}
	for i in range(n):
		curr = dist[i]
		if curr not in mp:
			mp[curr] = []
		mp[curr].append(i)
	for (k, v) in mp.items():
		if len(v) > 1:
			f = v[0]
			s = v[1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	mp1 = {}
	for i in range(n):
		for j in range(i + 1, n):
			curr = dist[i] ^ dist[j]
			if curr not in mp1:
				mp1[curr] = []
			mp1[curr].append([i, j])
			if len(mp1[curr]) > 1:
				print(mp1[curr][0][0] + 1, mp1[curr][0][1] + 1, mp1[curr][1][0] + 1, mp1[curr][1][1] + 1)
				return
	print(-1)
	return
for _ in range(int(input())):
	main()


from collections import defaultdict

def dfs(adj_list, node, visited, distances):
	visited[node] = True
	for (neighbor, weight) in adj_list[node]:
		if not visited[neighbor]:
			distances[neighbor] = distances[node] ^ weight
			dfs(adj_list, neighbor, visited, distances)

def find_path():
	n = int(input())
	adj_list = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj_list[u].append((v, w))
		adj_list[v].append((u, w))
	distances = [0] * n
	visited = [False] * n
	dfs(adj_list, 0, visited, distances)
	mp = defaultdict(list)
	for i in range(n):
		mp[distances[i]].append(i)
	for (key, value) in mp.items():
		if len(value) > 1:
			(f, s) = (value[0], value[1])
			if f == 0 and s == n - 1:
				print('1 2 2', n - 1)
			elif f == 0:
				print('1', n - 1, s + 1, n - 1)
			elif s == n - 1:
				print('1', f + 1, '1', s + 1)
			else:
				print('1', f + 1, '1', s + 1)
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[distances[i] ^ distances[j]].append([i, j])
			if len(mp2[distances[i] ^ distances[j]]) > 1:
				(a, b) = (mp2[distances[i] ^ distances[j]][0], mp2[distances[i] ^ distances[j]][1])
				print(a[0] + 1, a[1] + 1, b[0] + 1, b[1] + 1)
				return
	print(-1)
t = int(input())
for _ in range(t):
	find_path()


import sys
from collections import defaultdict

def solve():
	n = int(input())
	adj = defaultdict(list)
	for i in range(n - 1):
		(p, q, r) = map(int, input().split())
		adj[p - 1].append((q - 1, r))
		adj[q - 1].append((p - 1, r))
	vis = [0] * n
	dist = [0] * n

	def dfs(node, d):
		vis[node] = 1
		dist[node] = d
		for (q, r) in adj[node]:
			if not vis[q]:
				dfs(q, d ^ r)
	dfs(0, 0)
	s = defaultdict(list)
	for (i, d) in enumerate(dist):
		s[d].append(i)
	for (k, q) in s.items():
		if len(q) > 1:
			(p, q) = (q[0], q[1])
			if p == 0 and q == n - 1:
				print(1, 2, 2, n - 1)
			elif p == 0:
				print(1, n - 1, q + 1, n - 1)
			elif q == n - 1:
				print(1, p + 1, 1, q + 1)
			else:
				print(1, p + 1, 1, q + 1)
			return
	s2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			s2[dist[i] ^ dist[j]].append((i, j))
			if len(s2[dist[i] ^ dist[j]]) > 1:
				(a, b) = s2[dist[i] ^ dist[j]][0]
				(c, d) = s2[dist[i] ^ dist[j]][1]
				print(a + 1, b + 1, c + 1, d + 1)
				return
	print(-1)
t = int(input())
for i in range(t):
	solve()


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)

def solve2(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			solve2(adj, x[0], vis, dis)

def solve():
	n = int(input())
	adj = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * n
	vis = [0] * n
	dist[0] = 0
	solve2(adj, 0, vis, dist)
	mp = defaultdict(list)
	for i in range(n):
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			f = x[1][0]
			s = x[1][1]
			if f == 0 and s == n - 1:
				print('1 2 2', n - 1)
			elif f == 0:
				print('1', n - 1, s + 1, n - 1)
			elif s == n - 1:
				print('1', f + 1, '1', s + 1)
			else:
				print('1', f + 1, '1', s + 1)
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[dist[i] ^ dist[j]].append([i, j])
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print('-1')
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict
for _ in range(int(input())):
	N = int(input())
	graph = defaultdict(set)
	for _ in range(N - 1):
		(u, v, w) = map(int, input().split())
		graph[u].add((v, w))
		graph[v].add((u, w))
	f = [False]
	ans = defaultdict(list)
	ind = [-1]

	def helper(node, parent, res, src):
		if not f[0]:
			for (child, w) in graph[node]:
				if child != parent:
					helper(child, node, res ^ w, src)
			if parent != -1:
				if ans[res]:
					if ans[res][0] not in [[src, node], [node, src]]:
						ans[res].append([src, node])
						f[0] = True
						ind[0] = res
				elif src != node:
					ans[res].append([src, node])
		return res
	for i in range(1, N + 1):
		helper(i, -1, 0, i)
	if ind[0] == -1:
		print(-1)
	else:
		tmp = ans[ind[0]]
		print(*tmp[0], *tmp[1])


def dfs(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			dfs(adj, x[0], vis, dis)

def evlos():
	nested = int(input())
	adj = [[] for i in range(nested)]
	for i in range(nested - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * nested
	vis = [0] * nested
	dfs(adj, 0, vis, dist)
	mp = {}
	for i in range(nested):
		mp[dist[i]] = mp.get(dist[i], []) + [i]
	for x in mp.items():
		if len(x[1]) > 1:
			(f, s) = (x[1][0], x[1][1])
			if f == 0 and s == nested - 1:
				print('1 2 2', nested - 1)
			elif f == 0:
				print('1', nested - 1, s + 1, nested - 1)
			elif s == nested - 1:
				print('1', f + 1, '1', s + 1)
			else:
				print('1', f + 1, '1', s + 1)
			return
	mp2 = {}
	for i in range(nested):
		for j in range(i + 1, nested):
			mp2[dist[i] ^ dist[j]] = mp2.get(dist[i] ^ dist[j], []) + [[i, j]]
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print(-1)
test = int(input())
for _ in range(test):
	evlos()


import sys
import math
import heapq
import bisect
from collections import defaultdict

def defval():
	return []

def dfs(v):
	Visited[v] = 1
	for x in adj[v]:
		if Visited[x[0]] == 0:
			dis[x[0]] = dis[v] ^ x[1]
			dfs(x[0])
t = int(input())
for _ in range(t):
	flag = False
	n = int(input())
	adj = defaultdict(defval)
	for j in range(n - 1):
		(u, v, w) = map(int, input().split())
		adj[u].append([v, w])
		adj[v].append([u, w])
	dis = [0] * (n + 1)
	Visited = [0] * (n + 1)
	dfs(1)
	d = defaultdict(defval)
	for i in range(1, n + 1):
		d[dis[i]].append(i)
	for j in d:
		if len(d[j]) > 1:
			(fir, sec) = (d[j][0], d[j][1])
			if fir == 1 and sec == n:
				print(1, 2, 2, n - 1)
			elif fir == 1:
				print(1, n - 1, sec, n - 1)
			else:
				print(1, fir, 1, sec)
			flag = True
			break
	if flag:
		continue
	d2 = defaultdict(defval)
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			check = dis[i] ^ dis[j]
			d2[check].append([i, j])
			if len(d2[check]) > 1:
				print(d2[check][0][0], d2[check][0][1], d2[check][1][0], d2[check][1][1])
				flag = True
				break
		if flag:
			break
	else:
		print(-1)


import sys
import math

def computeGCD(x, y):
	while y:
		(x, y) = (y, x % y)
	return abs(x)
from collections import defaultdict

def defval():
	return []

def dfs(v):
	vis[v] = 1
	for x in adj[v]:
		if vis[x[0]] == 0:
			dist[x[0]] = dist[v] ^ x[1]
			dfs(x[0])
t = int(input())
for _ in range(t):
	flag = False
	n = int(input())
	adj = defaultdict(defval)
	for j in range(n - 1):
		(u, v, w) = map(int, input().split())
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * (n + 1)
	vis = [0] * (n + 1)
	dfs(1)
	d = defaultdict(defval)
	for i in range(1, n + 1):
		d[dist[i]].append(i)
	for j in d:
		if len(d[j]) > 1:
			(fir, sec) = (d[j][0], d[j][1])
			if fir == 1 and sec == n:
				print(1, 2, 2, n - 1)
			elif fir == 1:
				print(1, n - 1, sec, n - 1)
			else:
				print(1, fir, 1, sec)
			flag = True
			break
	if flag:
		continue
	d2 = defaultdict(defval)
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			d2[dist[i] ^ dist[j]].append([i, j])
			if len(d2[dist[i] ^ dist[j]]) > 1:
				print(d2[dist[i] ^ dist[j]][0][0], d2[dist[i] ^ dist[j]][0][1], d2[dist[i] ^ dist[j]][1][0], d2[dist[i] ^ dist[j]][1][1])
				flag = True
				break
		if flag:
			break
	else:
		print(-1)


import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def riches(adj_list, node, visited, distances):
	visited[node] = True
	for (neighbor, weight) in adj_list[node]:
		if not visited[neighbor]:
			distances[neighbor] = distances[node] ^ weight
			riches(adj_list, neighbor, visited, distances)

def bold():
	n = int(input())
	ramu = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		ramu[u].append([v, w])
		ramu[v].append([u, w])
	fonotics = [0] * n
	guage = [0] * n
	fonotics[0] = 0
	riches(ramu, 0, guage, fonotics)
	mp = defaultdict(list)
	for i in range(n):
		mp[fonotics[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			f = x[1][0]
			s = x[1][1]
			if f == 0 and s == n - 1:
				print('1 2 2 ' + str(n - 1))
			elif f == 0:
				print('1 ' + str(n - 1) + ' ' + str(s + 1) + ' ' + str(n - 1))
			elif s == n - 1:
				print('1 ' + str(f + 1) + ' 1 ' + str(s + 1))
			else:
				print('1 ' + str(f + 1) + ' 1 ' + str(s + 1))
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[fonotics[i] ^ fonotics[j]].append([i, j])
			if len(mp2[fonotics[i] ^ fonotics[j]]) > 1:
				print(str(mp2[fonotics[i] ^ fonotics[j]][0][0] + 1) + ' ' + str(mp2[fonotics[i] ^ fonotics[j]][0][1] + 1) + ' ' + str(mp2[fonotics[i] ^ fonotics[j]][1][0] + 1) + ' ' + str(mp2[fonotics[i] ^ fonotics[j]][1][1] + 1))
				return
	print('-1')
t = int(input())
for i in range(t):
	bold()


from collections import defaultdict

def dfs(node, parent, adj, vis, dis):
	vis[node] = True
	for (nei, w) in adj[node]:
		if nei != parent:
			dis[nei] = dis[node] ^ w
			dfs(nei, node, adj, vis, dis)

def solve():
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		adj[u - 1].append((v - 1, w))
		adj[v - 1].append((u - 1, w))
	vis = [False] * n
	dis = [0] * n
	dfs(0, -1, adj, vis, dis)
	dist_map = defaultdict(list)
	for (i, d) in enumerate(dis):
		dist_map[d].append(i)
	if len(dist_map) == 1:
		(u, v) = (dist_map[0][0], dist_map[0][-1])
		if u == 0 and v == n - 1:
			print(1, 2, 2, n - 1)
		elif u == 0:
			print(1, n - 1, v + 1, n - 1)
		elif v == n - 1:
			print(1, u + 1, 1, v + 1)
		else:
			print(1, u + 1, 1, v + 1)
	else:
		xor_map = defaultdict(list)
		for i in range(n):
			for j in range(i + 1, n):
				xor_map[dis[i] ^ dis[j]].append((i, j))
				if len(xor_map[dis[i] ^ dis[j]]) == 2:
					(u1, v1) = xor_map[dis[i] ^ dis[j]][0]
					(u2, v2) = xor_map[dis[i] ^ dis[j]][1]
					print(u1 + 1, v1 + 1, u2 + 1, v2 + 1)
					return
		print(-1)
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict

def solve2(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			solve2(adj, x[0], vis, dis)

def solve():
	n = int(input())
	adj = defaultdict(list)
	for i in range(n - 1):
		(r, g, w) = map(int, input().split())
		r -= 1
		g -= 1
		adj[r].append((g, w))
		adj[g].append((r, w))
	dist = [0] * n
	vis = [0] * n
	dist[0] = 0
	solve2(adj, 0, vis, dist)
	mp = defaultdict(list)
	for i in range(n):
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			f = x[1][0]
			s = x[1][1]
			if f == 0 and s == n - 1:
				print('1 2 2', n - 1)
			elif f == 0:
				print('1', n - 1, s + 1, n - 1)
			elif s == n - 1:
				print('1', f + 1, '1', s + 1)
			else:
				print('1', f + 1, '1', s + 1)
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[dist[i] ^ dist[j]].append((i, j))
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print('-1')
t = int(input())
for _ in range(t):
	solve()


from typing import List, Tuple
import sys
sys.setrecursionlimit(10 ** 6)

def dfs(adj_list: List[List[Tuple[int, int]]], node: int, visited: List[int], distance: List[int]) -> None:
	visited[node] = 1
	for (v, w) in adj_list[node]:
		if not visited[v]:
			distance[v] = distance[node] ^ w
			dfs(adj_list, v, visited, distance)

def solve() -> None:
	n = int(input())
	adj_list = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj_list[u].append((v, w))
		adj_list[v].append((u, w))
	dist = [0] * n
	visited = [0] * n
	dist[0] = 0
	dfs(adj_list, 0, visited, dist)
	mp = {}
	for i in range(n):
		if dist[i] in mp:
			mp[dist[i]].append(i)
		else:
			mp[dist[i]] = [i]
	for (k, v) in mp.items():
		if len(v) > 1:
			f = v[0]
			s = v[1]
			if f == 0 and s == n - 1:
				print('1 2 2', n - 1)
			elif f == 0:
				print('1', n - 1, s + 1, n - 1)
			elif s == n - 1:
				print('1', f + 1, '1', s + 1)
			else:
				print('1', f + 1, '1', s + 1)
			return
	mp2 = {}
	for i in range(n):
		for j in range(i + 1, n):
			if dist[i] ^ dist[j] in mp2:
				mp2[dist[i] ^ dist[j]].append([i, j])
			else:
				mp2[dist[i] ^ dist[j]] = [[i, j]]
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print('-1')
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict

def dfs(adj1, node1, vis1, dis1):
	vis1[node1] = 1
	for x1 in adj1[node1]:
		if not vis1[x1[0]]:
			dis1[x1[0]] = dis1[node1] ^ x1[1]
			dfs(adj1, x1[0], vis1, dis1)

def solve():
	n1 = int(input())
	adj1 = defaultdict(list)
	for i in range(n1 - 1):
		(u1, v1, w1) = map(int, input().split())
		u1 -= 1
		v1 -= 1
		adj1[u1].append([v1, w1])
		adj1[v1].append([u1, w1])
	dist1 = [0] * n1
	vis1 = [0] * n1
	dfs(adj1, 0, vis1, dist1)
	mp = defaultdict(list)
	for i in range(n1):
		mp[dist1[i]].append(i)
	for x1 in mp.items():
		if len(x1[1]) > 1:
			(f1, s1) = (x1[1][0], x1[1][1])
			if f1 == 0 and s1 == n1 - 1:
				print(1, 2, 2, n1 - 1)
			elif f1 == 0:
				print(1, n1 - 1, s1 + 1, n1 - 1)
			elif s1 == n1 - 1:
				print(1, f1 + 1, 1, s1 + 1)
			else:
				print(1, f1 + 1, 1, s1 + 1)
			return
	mp2 = defaultdict(list)
	for i in range(n1):
		for j in range(i + 1, n1):
			mp2[dist1[i] ^ dist1[j]].append([i, j])
			if len(mp2[dist1[i] ^ dist1[j]]) > 1:
				print(mp2[dist1[i] ^ dist1[j]][0][0] + 1, mp2[dist1[i] ^ dist1[j]][0][1] + 1, mp2[dist1[i] ^ dist1[j]][1][0] + 1, mp2[dist1[i] ^ dist1[j]][1][1] + 1)
				return
	print(-1)
t1 = int(input())
for _ in range(t1):
	solve()


def dfs(adj_list, node, visited, distances):
	visited[node] = True
	for (neighbor, weight) in adj_list[node]:
		if not visited[neighbor]:
			distances[neighbor] = distances[node] ^ weight
			dfs(adj_list, neighbor, visited, distances)

def sol():
	num_nodes = int(input())
	adj_list = [[] for _ in range(num_nodes)]
	for i in range(num_nodes - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj_list[u].append((v, w))
		adj_list[v].append((u, w))
	distances = [0] * num_nodes
	visited = [False] * num_nodes
	distances[0] = 0
	dfs(adj_list, 0, visited, distances)
	distance_map = {}
	for i in range(num_nodes):
		if distances[i] in distance_map:
			distance_map[distances[i]].append(i)
		else:
			distance_map[distances[i]] = [i]
	for (k, v) in distance_map.items():
		if len(v) > 1:
			f = v[0]
			s = v[1]
			if f == 0 and s == num_nodes - 1:
				print(1, 2, 2, num_nodes - 1)
			elif f == 0:
				print(1, num_nodes - 1, s + 1, num_nodes - 1)
			elif s == num_nodes - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	distance_pairs = {}
	for i in range(num_nodes):
		for j in range(i + 1, num_nodes):
			xor_val = distances[i] ^ distances[j]
			if xor_val in distance_pairs:
				distance_pairs[xor_val].append((i, j))
				if len(distance_pairs[xor_val]) > 1:
					print(distance_pairs[xor_val][0][0] + 1, distance_pairs[xor_val][0][1] + 1, distance_pairs[xor_val][1][0] + 1, distance_pairs[xor_val][1][1] + 1)
					return
			else:
				distance_pairs[xor_val] = [(i, j)]
	print(-1)
t = int(input())
for _ in range(t):
	sol()


from collections import defaultdict

def fn(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			fn(adj, x[0], vis, dis)

def solve():
	n = int(input())
	adj = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * n
	vis = [0] * n
	dist[0] = 0
	fn(adj, 0, vis, dist)
	mp = defaultdict(list)
	for i in range(n):
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			f = x[1][0]
			s = x[1][1]
			if f == 0 and s == n - 1:
				print('1 2 2 ' + str(n - 1))
			elif f == 0:
				print('1 ' + str(n - 1) + ' ' + str(s + 1) + ' ' + str(n - 1))
			elif s == n - 1:
				print('1 ' + str(f + 1) + ' 1 ' + str(s + 1))
			else:
				print('1 ' + str(f + 1) + ' 1 ' + str(s + 1))
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[dist[i] ^ dist[j]].append([i, j])
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(str(mp2[dist[i] ^ dist[j]][0][0] + 1) + ' ' + str(mp2[dist[i] ^ dist[j]][0][1] + 1) + ' ' + str(mp2[dist[i] ^ dist[j]][1][0] + 1) + ' ' + str(mp2[dist[i] ^ dist[j]][1][1] + 1))
				return
	print('-1')
t = int(input())
for i in range(t):
	solve()


from collections import defaultdict

def solve2(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			solve2(adj, x[0], vis, dis)

def solve():
	n = int(input())
	adj = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * n
	vis = [0] * n
	dist[0] = 0
	solve2(adj, 0, vis, dist)
	mp = defaultdict(list)
	for i in range(n):
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			p = x[1][0]
			q = x[1][1]
			if p != 0 and q != n - 1:
				print(1, p + 1, 1, q + 1)
			elif q == n - 1:
				print(1, p + 1, 1, q + 1)
			elif p == 0:
				print(1, n - 1, q + 1, n - 1)
			else:
				print(1, 2, 2, n - 1)
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[dist[i] ^ dist[j]].append([i, j])
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print(-1)
a = int(input())
while a > 0:
	solve()
	a -= 1


import sys
sys.setrecursionlimit(10 ** 6)
SIZE = int(1000000.0 + 2)
JM = 1022
MOD = 1000000005 + 2

def dfs(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			dfs(adj, x[0], vis, dis)

def megha():
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * n
	vis = [0] * n
	dfs(adj, 0, vis, dist)
	mp = {}
	for i in range(n):
		if dist[i] in mp:
			mp[dist[i]].append(i)
		else:
			mp[dist[i]] = [i]
	for (key, val) in mp.items():
		if len(val) > 1:
			f = val[0]
			s = val[1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	mp2 = {}
	for i in range(n):
		for j in range(i + 1, n):
			if dist[i] ^ dist[j] in mp2:
				mp2[dist[i] ^ dist[j]].append([i, j])
			else:
				mp2[dist[i] ^ dist[j]] = [[i, j]]
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print(-1)
ct = int(input())
for x in range(ct):
	megha()


from collections import defaultdict

def answer():
	n = int(input())
	adj = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append((v, w))
		adj[v].append((u, w))
	dist = [0] * n
	vis = [0] * n
	traversal(0, adj, vis, dist)
	mp = defaultdict(list)
	for i in range(n):
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			f = x[1][0]
			s = x[1][1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[dist[i] ^ dist[j]].append((i, j))
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print(-1)

def traversal(node, adj, vis, dist):
	vis[node] = 1
	for (v, w) in adj[node]:
		if not vis[v]:
			dist[v] = dist[node] ^ w
			traversal(v, adj, vis, dist)
tc = int(input())
for i in range(tc):
	answer()


import sys
from collections import defaultdict

def dfs(adj_list, node, visited, distance):
	visited[node] = True
	for (neighbor, weight) in adj_list[node]:
		if not visited[neighbor]:
			distance[neighbor] = distance[node] ^ weight
			dfs(adj_list, neighbor, visited, distance)

def find_path(n, edges):
	adj_list = defaultdict(list)
	for (u, v, w) in edges:
		u -= 1
		v -= 1
		adj_list[u].append((v, w))
		adj_list[v].append((u, w))
	distances = [0] * n
	visited = [False] * n
	distances[0] = 0
	dfs(adj_list, 0, visited, distances)
	dist_map = defaultdict(list)
	for i in range(n):
		dist_map[distances[i]].append(i)
	for (dist, nodes) in dist_map.items():
		if len(nodes) > 1:
			f = nodes[0]
			s = nodes[1]
			if f == 0 and s == n - 1:
				return [1, 2, 2, n - 1]
			elif f == 0:
				return [1, n - 1, s + 1, n - 1]
			elif s == n - 1:
				return [1, f + 1, 1, s + 1]
			else:
				return [1, f + 1, 1, s + 1]
	dist_edge_map = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			dist_edge_map[distances[i] ^ distances[j]].append([i, j])
			if len(dist_edge_map[distances[i] ^ distances[j]]) > 1:
				edge1 = dist_edge_map[distances[i] ^ distances[j]][0]
				edge2 = dist_edge_map[distances[i] ^ distances[j]][1]
				return [edge1[0] + 1, edge1[1] + 1, edge2[0] + 1, edge2[1] + 1]
	return [-1]
t = int(input())
for _ in range(t):
	n = int(input())
	edges = []
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		edges.append((u, v, w))
	path = find_path(n, edges)
	print(*path)


from collections import defaultdict

def dfs(adj_list, node, visited, distance):
	visited[node] = True
	for (neighbour, weight) in adj_list[node]:
		if not visited[neighbour]:
			distance[neighbour] = distance[node] ^ weight
			dfs(adj_list, neighbour, visited, distance)

def find_path(n, adj_list):
	distance = [0] * n
	visited = [False] * n
	dfs(adj_list, 0, visited, distance)
	path = defaultdict(list)
	for i in range(n):
		path[distance[i]].append(i)
	for (dist, nodes) in path.items():
		if len(nodes) > 1:
			(f, s) = (nodes[0], nodes[1])
			if f == 0 and s == n - 1:
				return [1, 2, 2, n - 1]
			elif f == 0:
				return [1, n - 1, s + 1, n - 1]
			elif s == n - 1:
				return [1, f + 1, 1, s + 1]
			else:
				return [1, f + 1, 1, s + 1]
	return None

def find_cycle(n, adj_list):
	distance = [0] * n
	visited = [False] * n
	dfs(adj_list, 0, visited, distance)
	cycle = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			cycle[distance[i] ^ distance[j]].append([i, j])
			if len(cycle[distance[i] ^ distance[j]]) > 1:
				return [cycle[distance[i] ^ distance[j]][0][0] + 1, cycle[distance[i] ^ distance[j]][0][1] + 1, cycle[distance[i] ^ distance[j]][1][0] + 1, cycle[distance[i] ^ distance[j]][1][1] + 1]
	return None

def solve():
	n = int(input())
	adj_list = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj_list[u].append([v, w])
		adj_list[v].append([u, w])
	path = find_path(n, adj_list)
	if path:
		print(*path)
		return
	cycle = find_cycle(n, adj_list)
	if cycle:
		print(*cycle)
		return
	print(-1)
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict

def dfs(adj_list, node, visited, distance):
	visited[node] = 1
	for x in adj_list[node]:
		if not visited[x[0]]:
			distance[x[0]] = distance[node] ^ x[1]
			dfs(adj_list, x[0], visited, distance)

def solve():
	n = int(input())
	adj_list = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj_list[u].append([v, w])
		adj_list[v].append([u, w])
	distance = [0] * n
	visited = [0] * n
	distance[0] = 0
	dfs(adj_list, 0, visited, distance)
	mp = defaultdict(list)
	for i in range(n):
		mp[distance[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			(f, s) = (x[1][0], x[1][1])
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[distance[i] ^ distance[j]].append([i, j])
			if len(mp2[distance[i] ^ distance[j]]) > 1:
				print(mp2[distance[i] ^ distance[j]][0][0] + 1, mp2[distance[i] ^ distance[j]][0][1] + 1, mp2[distance[i] ^ distance[j]][1][0] + 1, mp2[distance[i] ^ distance[j]][1][1] + 1)
				return
	print(-1)
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict

def iareobaergb(aj, nde, vis, dis):
	vis[nde] = 1
	for x in aj[nde]:
		if not vis[x[0]]:
			dis[x[0]] = dis[nde] ^ x[1]
			iareobaergb(aj, x[0], vis, dis)

def rfoywefooabrvub():
	n = int(input())
	aj = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		aj[u].append([v, w])
		aj[v].append([u, w])
	dist = [0] * n
	vis = [0] * n
	dist[0] = 0
	iareobaergb(aj, 0, vis, dist)
	m = defaultdict(list)
	for i in range(n):
		m[dist[i]].append(i)
	for q in m.items():
		if len(q[1]) > 1:
			f = q[1][0]
			s = q[1][1]
			if f == 0 and s == n - 1:
				print('1 2 2', n - 1)
			elif f == 0:
				print('1', n - 1, s + 1, n - 1)
			elif s == n - 1:
				print('1', f + 1, '1', s + 1)
			else:
				print('1', f + 1, '1', s + 1)
			return
	m2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			m2[dist[i] ^ dist[j]].append([i, j])
			if len(m2[dist[i] ^ dist[j]]) > 1:
				print(m2[dist[i] ^ dist[j]][0][0] + 1, m2[dist[i] ^ dist[j]][0][1] + 1, m2[dist[i] ^ dist[j]][1][0] + 1, m2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print('-1')
g = int(input())
for _ in range(g):
	rfoywefooabrvub()


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	g = defaultdict(list)
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		g[u].append((v, w))
		g[v].append((u, w))
	d = [0] * (n + 1)

	def dfs(x, p):
		for (y, k) in g[x]:
			if y != p:
				d[y] = k ^ d[x]
				dfs(y, x)
	dfs(1, 0)
	fa = False
	grp = defaultdict(list)
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			x = d[i] ^ d[j]
			grp[x].append((i, j))
			if len(grp[x]) > 1:
				fa = True
				res = [grp[x][0], grp[x][1]]
				break
		if fa:
			break
	if fa:
		print(*res[0], *res[1])
	else:
		print(-1)


import collections

def answer(arr, conn, vectorr, two):
	vectorr[conn] = 1
	for j in arr[conn]:
		if not vectorr[j[0]]:
			two[j[0]] = two[conn] ^ j[1]
			answer(arr, j[0], vectorr, two)

def solve():
	n = int(input())
	arr = [[] for i in range(n)]
	for i in range(n - 1):
		(ss, tt, uu) = map(int, input().split())
		ss -= 1
		tt -= 1
		arr[ss].append([tt, uu])
		arr[tt].append([ss, uu])
	one = [0] * n
	two = [0] * n
	one[0] = 0
	answer(arr, 0, two, one)
	nop = collections.defaultdict(list)
	for i in range(n):
		nop[one[i]].append(i)
	for jk in nop.items():
		if len(jk[1]) > 1:
			flag1 = jk[1][0]
			flag2 = jk[1][1]
			if flag1 == 0 and flag2 == n - 1:
				print(1, 2, 2, n - 1)
			elif flag1 == 0:
				print(1, n - 1, flag2 + 1, n - 1)
			elif flag2 == n - 1:
				print(1, flag1 + 1, 1, flag2 + 1)
			else:
				print(1, flag1 + 1, 1, flag2 + 1)
			return
	arr2 = collections.defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			arr2[one[i] ^ one[j]].append([i, j])
			if len(arr2[one[i] ^ one[j]]) > 1:
				print(arr2[one[i] ^ one[j]][0][0] + 1, arr2[one[i] ^ one[j]][0][1] + 1, arr2[one[i] ^ one[j]][1][0] + 1, arr2[one[i] ^ one[j]][1][1] + 1)
				return
	print(-1)
t = int(input())
for i in range(t):
	solve()


from collections import defaultdict

def imp_fun(adjascency_lst, node, visited_vec, distance_vec):
	visited_vec[node] = 1
	for iter in adjascency_lst[node]:
		if visited_vec[iter[0]] == 0:
			distance_vec[iter[0]] = distance_vec[node] ^ iter[1]
			imp_fun(adjascency_lst, iter[0], visited_vec, distance_vec)
t = int(input())
for i in range(t):
	n = int(input())
	adjascency_lst = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		adjascency_lst[u - 1].append([v - 1, w])
		adjascency_lst[v - 1].append([u - 1, w])
	distance_vect = [0] * n
	visited_vec = [0] * n
	distance_vect[0] = 0
	imp_fun(adjascency_lst, 0, visited_vec, distance_vect)
	mp = defaultdict(list)
	for i in range(n):
		mp[distance_vect[i]].append(i)
	er = 0
	for iter in mp.items():
		if len(iter[1]) > 1:
			f = iter[1][0]
			s = iter[1][1]
			if s == n - 1:
				print(1, f + 1, 1, s + 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			else:
				print(1, f + 1, 1, s + 1)
			er += 1
			break
	if er > 0:
		continue
	second_map = defaultdict(list)
	for i in range(n):
		if er > 0:
			break
		for j in range(i + 1, n):
			if er > 0:
				break
			second_map[distance_vect[i] ^ distance_vect[j]].append([i, j])
			if len(second_map[distance_vect[i] ^ distance_vect[j]]) > 1:
				print(second_map[distance_vect[i] ^ distance_vect[j]][0][0] + 1, second_map[distance_vect[i] ^ distance_vect[j]][0][1] + 1, second_map[distance_vect[i] ^ distance_vect[j]][1][0] + 1, second_map[distance_vect[i] ^ distance_vect[j]][1][1] + 1)
				er += 1
				break
		if er > 0:
			continue
	if er > 0:
		continue
	print(-1)


mod = 10 ** 9 + 7

def checkerforlecker(adj, node, dis, vis):
	vis[node] = 1
	for it in adj[node]:
		if not vis[it[0]]:
			dis[it[0]] = dis[node] ^ it[1]
			checkerforlecker(adj, it[0], dis, vis)

def harukicheck2():
	n = int(input())
	res = 0
	pakkachakka = 1
	v = []
	panipani = {}
	for x in map(int, input().split()):
		panipani[x] = panipani.get(x, 0) + 1
	for i in range(1, n + 1):
		temp = pakkachakka * panipani.get(i, 0)
		temp %= mod
		res += temp
		pakkachakka = temp
		res %= mod
	print(res)

def harukicheck():
	n = int(input())
	adj = [[] for i in range(n)]
	(fullpeck, vis) = ([0] * n, [0] * n)
	for i in range(n - 1):
		(edgeu, edgy, w) = map(int, input().split())
		edgeu -= 1
		edgy -= 1
		adj[edgeu].append([edgy, w])
		adj[edgy].append([edgeu, w])
	fullpeck[0] = 0
	checkerforlecker(adj, 0, fullpeck, vis)
	pepper = {}
	for i in range(n):
		pepper[fullpeck[i]] = pepper.get(fullpeck[i], []) + [i]
	for (k, value) in pepper.items():
		if len(value) >= 2:
			f = value[0]
			s = value[1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	pepper2 = {}
	for i in range(n):
		for j in range(i + 1, n):
			pepper2[fullpeck[i] ^ fullpeck[j]] = pepper2.get(fullpeck[i] ^ fullpeck[j], []) + [[i, j]]
			if len(pepper2[fullpeck[i] ^ fullpeck[j]]) >= 2:
				print(pepper2[fullpeck[i] ^ fullpeck[j]][0][0] + 1, pepper2[fullpeck[i] ^ fullpeck[j]][0][1] + 1, pepper2[fullpeck[i] ^ fullpeck[j]][1][0] + 1, pepper2[fullpeck[i] ^ fullpeck[j]][1][1] + 1)
				return
	print(-1)
t = int(input())
while t > 0:
	harukicheck()
	t -= 1


from collections import defaultdict

def func(adjacent, node, visited, distance):
	visited[node] = 1
	for i in adjacent[node]:
		if not visited[i[0]]:
			distance[i[0]] = distance[node] ^ i[1]
			func(adjacent, i[0], visited, distance)

def solve():
	n = int(input())
	adjacent = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adjacent[u].append([v, w])
		adjacent[v].append([u, w])
	distance = [0] * n
	visited = [0] * n
	distance[0] = 0
	func(adjacent, 0, visited, distance)
	result = defaultdict(list)
	for i in range(n):
		result[distance[i]].append(i)
	for j in result.items():
		if len(j[1]) > 1:
			(a, b) = (j[1][0], j[1][1])
			if a == 0 and b == n - 1:
				print(1, 2, 2, n - 1)
			elif a == 0:
				print(1, n - 1, b + 1, n - 1)
			elif b == n - 1:
				print(1, a + 1, 1, b + 1)
			else:
				print(1, a + 1, 1, b + 1)
			return
	result2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			result2[distance[i] ^ distance[j]].append([i, j])
			if len(result2[distance[i] ^ distance[j]]) > 1:
				print(result2[distance[i] ^ distance[j]][0][0] + 1, result2[distance[i] ^ distance[j]][0][1] + 1, result2[distance[i] ^ distance[j]][1][0] + 1, result2[distance[i] ^ distance[j]][1][1] + 1)
				return
	print(-1)
t = int(input())
for _ in range(t):
	solve()


def countingSort(arr, exp1):
	n = len(arr)
	output = [0] * n
	count = [0] * 10
	for i in range(0, n):
		index = arr[i] // exp1
		count[index % 10] += 1
	for i in range(1, 10):
		count[i] += count[i - 1]
	i = n - 1
	while i >= 0:
		index = arr[i] // exp1
		output[count[index % 10] - 1] = arr[i]
		count[index % 10] -= 1
		i -= 1
	i = 0
	for i in range(0, len(arr)):
		arr[i] = output[i]

def radixSort(arr):
	max1 = max(arr)
	exp = 1
	while max1 / exp >= 1:
		countingSort(arr, exp)
		exp *= 10

def fn(adj, node, vis, dis):
	vis[node] = 1
	for x in adj[node]:
		if not vis[x[0]]:
			dis[x[0]] = dis[node] ^ x[1]
			fn(adj, x[0], vis, dis)

def solve():
	n = int(input())
	adj = [[] for _ in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append([v, w])
		adj[v].append([u, w])
	dist = [0] * n
	vis = [0] * n
	dist[0] = 0
	fn(adj, 0, vis, dist)
	mp = {}
	for i in range(n):
		if dist[i] not in mp:
			mp[dist[i]] = []
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			f = x[1][0]
			s = x[1][1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	mp2 = {}
	for i in range(n):
		for j in range(i + 1, n):
			if dist[i] ^ dist[j] not in mp2:
				mp2[dist[i] ^ dist[j]] = []
			mp2[dist[i] ^ dist[j]].append([i, j])
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print(-1)
t = int(input())
for _ in range(t):
	solve()


from collections import defaultdict

def dfs(adj_list, node, vis, dist):
	vis[node] = True
	for (v, w) in adj_list[node]:
		if not vis[v]:
			dist[v] = dist[node] ^ w
			dfs(adj_list, v, vis, dist)

def solve():
	n = int(input())
	adj_list = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		adj_list[u].append((v, w))
		adj_list[v].append((u, w))
	dist = [0] * n
	vis = [False] * n
	dfs(adj_list, 0, vis, dist)
	mp = defaultdict(list)
	for i in range(n):
		mp[dist[i]].append(i)
	for x in mp.items():
		if len(x[1]) > 1:
			f = x[1][0]
			s = x[1][1]
			if f == 0 and s == n - 1:
				print(1, 2, 2, n - 1)
			elif f == 0:
				print(1, n - 1, s + 1, n - 1)
			elif s == n - 1:
				print(1, f + 1, 1, s + 1)
			else:
				print(1, f + 1, 1, s + 1)
			return
	mp2 = defaultdict(list)
	for i in range(n):
		for j in range(i + 1, n):
			mp2[dist[i] ^ dist[j]].append([i, j])
			if len(mp2[dist[i] ^ dist[j]]) > 1:
				print(mp2[dist[i] ^ dist[j]][0][0] + 1, mp2[dist[i] ^ dist[j]][0][1] + 1, mp2[dist[i] ^ dist[j]][1][0] + 1, mp2[dist[i] ^ dist[j]][1][1] + 1)
				return
	print(-1)
t = int(input())
while t:
	solve()
	t -= 1