ghc很喜欢吃汤圆，但是汤圆很容易被粘(zhān)漏。

根据多年吃汤圆经验，ghc总结出了一套汤圆防漏理论：

互相接触的汤圆容易粘(zhān)在一起，并且接触面积不同，粘(zhān)在一起的粘(nián)度也不同。

当ghc要夹起一个汤圆时，这个汤圆和现在碗里与这个汤圆接触的所有汤圆之间的粘(nián)度的和，如果大于汤圆的硬度，这个汤圆就会被粘(zhān)漏。

今天ghc又要煮汤圆啦，今天要煮个汤圆，并且摆盘的方法已经设计好：

汤圆按照编号，有对汤圆互相接触，用表示编号为和的两个汤圆互相接触，粘(nián)度为。

汤圆当然是越软越好吃，但是ghc的厨艺只允许把所有汤圆煮成同样的硬度。那么，汤圆的硬度最小可以是多少，可以满足吃的过程中，存在一种夹汤圆的顺序，使得没有汤圆会被粘(zhān)漏呢？

注意：

不考虑汤圆的重力作用；

不能同时夹多个汤圆；

吃完汤圆一定要喝点汤。

 

Input

第一行是一个正整数，表示测试数据的组数，

对于每组测试数据，

第一行是两个整数，

接下来行，每行包含三个整数，

同一对汤圆不会出现两次。

 

Output

对于每组测试数据，输出一行，包含一个整数，表示汤圆硬度的最小值。

 

Sample Input

14 61 2 21 3 21 4 22 3 32 4 33 4 5

Sample Output

6

#include
     
      using namespace std;const int N = 1e5 + 5;using LL = long long;using P = pair
      
       ;LL cnt[N];int n, m;set
       
 edge[N];priority_queue
        
         , greater
        
       
 > Q;void Work(){    LL ans = 0;    for(int i = 1; i <= n; i++){        Q.push({cnt[i], i});    }    while(!Q.empty()){        auto tmp = Q.top(); Q.pop();        if(tmp.first != cnt[tmp.second]) continue;        int u = tmp.second;        ans = max(ans, tmp.first);        for(auto p : edge[u]){            int v = p.second;            cnt[v] -= p.first;            edge[v].erase({p.first, u});            Q.push({cnt[v], v});        }    }    cout << ans << endl;}int main(){   int T;   cin >> T;   while(T--){       cin >> n >> m;       for(int i = 1; i <= n; i++) {            edge[i].clear();            cnt[i] = 0;       }       int u, v, w;       for(int i = 1; i <= m; i++){            cin >> u >> v >> w;            cnt[u] += w;            cnt[v] += w;            edge[u].insert({w, v});            edge[v].insert({w, u});       }       Work();   }}