quantitative-coefficient

Russian Translation Available

It is very important to understand relationship between variables to draw the right conclusion from a statistical analysis. The relationship between variables determines how the right conclusions are reached. Without an understanding of this, you can fall into many pitfalls that accompany statistical analysis and infer wrong results from your data.

Linear programming (LP; also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints.

We are not going to present some LP theory, but let's have a look at combinatorial problem related to this theory.
Suppose you have a set of N variables. There are M relationships of some pairs of these variables. More formally, you have M relationships of type ai, bi, ci which means that variables ai and bi are in a relationship with quantitative coefficient ci. Quantitative coefficient of a connected set S of variables is a product of all relationship quantitative coefficients in this set.

Set S of variables is called connected if any two variables in this set are connected. Variables x and y are called connected if at least one of the following conditions is satisfied:
x and y are put in relationship directly
there is such a variable z that x and z are connected and y and z are connected too.

You are given a connected set S of N variables and M relationships. Your task is to leave some of these relationships in such a way that S is still connected and its quantitative coefficient is minimal possible.

Input

The first line contains one integer T denoting the number of test cases.
Each test case starts with a line containing 2 space-separated integer: N and M. Each of the following M lines contain description of one relationship: three different space-separated integers: a, b and c. a and b are different and from 1 to N each and denote numbers of vertices that are connected by this edge. c denotes quantitative coefficient of this relationship. It's guaranteed that the given set is initially connected. 

Output

For each test case output one integer - minimal possible quantitative coefficient. As the the answer can be very big output it modulo 10^9 + 7.

Constraints
1 ≤ T ≤ 20
1 ≤ N ≤ 1500
1 ≤ M ≤ 31313
1 ≤ ai, bi ≤ N
1 ≤ ci ≤ 10^9

SAMPLE INPUT
1
3 3
1 2 1234567
2 3 2345678
1 3 3456789


SAMPLE OUTPUT
896631161

Source: hackerearth | Difficulty: EASY


Solutions:
import heapq
for _ in range(eval(input())):
	node,edge=list(map(int,input().split()))
	heap=[[1,1]]
	visit=[0 for _ in range(node+1)]
	arr=[[] for _ in range(node+1)]
	for _ in range(edge):
		a,b,c=list(map(int,input().split()))
		arr[a].append([c,b])
		arr[b].append([c,a])
	maximum=1
	while len(heap)>0:
		x,y=heapq.heappop(heap)
		
	#	print maximum,x,
		if visit[y]==1:continue
		maximum=((maximum%1000000007)*(x%1000000007))%1000000007
		visit[y]=1
		for s in arr[y]:
			if visit[s[1]]==0:
				heapq.heappush(heap,s)
	print(maximum)
			
		
	


from collections import defaultdict

def make_set(N):
	global parents
       
	for node in range(1,N+1):
	    parents[node] = node
	    
	    
def Union(node1,node2):
	global parents
	   
	node1_root = Find(node1)
	node2_root = Find(node2)

	if node1_root == node2_root:
	     return
	
	parents[node1_root] = node2_root

	
	    
def Find(node):
	global parents
	if parents[node] != node:
	    parents[node] = Find(parents[node])    
	return parents[node]




def Krushkal(weighted_edge_list=[],N=0):
     
	count,cost = 0,1
	
	make_set(N)
	weighted_edge_list.sort(key=lambda x:x[2])
      
	for edge in weighted_edge_list:
	    
	    root1 = Find(edge[0])
	    root2 = Find(edge[1])
	
	    if root1 != root2:
		Union(root1,root2)
		count+=1
		
		cost *= edge[2]
		
	    if count == N-1:
		 break
		
	return cost 


t = int(input())

while t>0:
    N,M    = [int(x) for x in input().split()]
    edges  = []
    parents = [0]*10**6

    for i in range(M):
	node = [int(x) for x in input().split()]
	edges.append(node)

    
    print((Krushkal(edges,N))%1000000007)
    

    t -= 1


import collections
import heapq

MOD = 1000000007

def mst(graph, n):
	total = 1
	seen = set([1])
	q = graph[1]
	heapq.heapify(q)
	while q:
		cost, node = heapq.heappop(q)
		if node in seen: continue
		seen.add(node)
		total = (total * cost) % MOD
		if len(seen) == n: break
		for child in graph[node]:
			heapq.heappush(q, child)
	return total

def solve(n, mss):
	graph = collections.defaultdict(list)
	for a, b, cost in mss:
		graph[a].append((cost, b))
		graph[b].append((cost, a))
	return mst(graph, n)

if __name__ == '__main__':
	for _ in range(int(input())):
		n, m = list(map(int, input().split()))
		mss = [list(map(int, input().split())) for _ in range(m)]
		print(solve(n, mss))