import sys
from math import log
from heapq import heappush,heappop
def main():
all=sys.stdin.readlines()
t=int(all[0])
lno=1
for h in xrange(t):
n,m=(int(p) for p in all[lno].split())
lno+=1
if n==0:
print '0'
continue
graph=[ [] for i in xrange(n+1) ]
for k in xrange(m):
a,b,c=(int(p) for p in all[lno].split())
lno+=1
c=int(log(c,2))
graph[a].append((c,b))
graph[b].append((c,a))
#prim's:
mst=0
vertex = [0 for i in xrange(n+1)]
heapedge = []
v=1
vertex[1]=1
b=1
while v<n:
for c,a in graph[b]:
if vertex[a]==0:
heappush(heapedge,(c,a))
while vertex[b]==1:
c,b=heappop(heapedge)
vertex[b]=1
mst+=c
v+=1
print mst+1
if __name__=='__main__':
main()
