e_noether
Sep '13

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()