'''cpp
include<bits/stdc++.h>
include
using namespace std;
const int N = 505;
int n , m;
map<int,vector<pair<int,int>>>E;
map<int,int>limit;
typedef long long ll;
struct uni {
int p[N];
int cnt ;
void init() {
for(int i = 1; i <= n; i++) p[i] = i;
cnt = n;
}
int Find(int x) {
return p[x] == x ? x : p[x] = Find(p[x]) ;
}
bool Merge(int u,int v) {
u = Find(u) , v = Find(v);
if(u == v) return 0;
p[u] = v;
cnt--;
return 1;
}
bool in(int u,int v) {
return Find(u) == Find(v);
}
} Un[N];
struct edge {
int u , v , w;
};
struct Item {
int x,y,col;
ll val;
Item() {}
Item(int _x,int _y,int _col,ll _val) {
x=_x;
y=_y;
col=_col;
val=_val;
}
};
namespace Matroid {
///F1 : connect
///F2 : num limit
const int M=N2,E=100005;
const ll inf=1e9;
int n,tot,ans,S,T,g[M],v[E],nxt[E],ed,q[E],h,t,d[M],pre[M],w[M];
map<int,int>cnt;
bool in[M],use[M];
Item item[M];
inline void add(int x,int y) {
v[++ed]=y;
nxt[ed]=g[x];
g[x]=ed;
}
inline void ext(int x,int y,int z) {
if(d[x]>=y)return;
d[x]=y;
pre[x]=z;
if(in[x])return;
q[++t]=x;
in[x]=1;
}
inline bool find() {
int i,j,S=n+1,T=n+2;
for(ed=i=0; i<=T; i++)g[i]=w[i]=0;
for(int i = 0; i < n; i++) {//维护所有的I+{x}
if(!use[i]) {
Un[i].init() ;
for(int j = 0; j < n; j++) {
if(i != j&&(!use[j])) Un[i].Merge(item[j].x , item[j].y);
}
}
}
for(i=0; i<n; i++)if(!use[i]) {
w[i]=item[i].val;
use[i]^=1;
cnt[item[i].col]++;
if(Un[i].cnt == 1)add(S,i);//I+{i}\in F1
if(cnt[item[i].col]<=limit[item[i].col])add(i,T);//I+{i}\in F2
cnt[item[i].col]--;
use[i]^=1;
} else w[i]=-item[i].val;
for(i=0; i<n; i++)if(use[i])for(j=0; j<n; j++)if(!use[j]) {
use[i]=1,use[j]=1;
cnt[item[i].col]--;
cnt[item[j].col]++;
if(Un[j].cnt == 1 || (Un[j].cnt == 2 && (!Un[j].in(item[i].x,item[i].y))))add(i,j);//I-{i}+{j}\in F1
if(cnt[item[j].col]<=limit[item[j].col])add(j,i);//I-{i}+{j}\in F2
cnt[item[i].col]++;
cnt[item[j].col]--;
use[i]=1,use[j]=1;
}
for(i=0; i<=T; i++)d[i]=-inf,in[i]=0;
q[h=t=1]=S;
d[S]=0,in[S]=1;
while(h<=t) {
int x=q[h++];
for(i=g[x]; i; i=nxt[i])ext(v[i],d[x]+w[v[i]],x);
in[x]=0;
}
if(d[T]==-inf)return 0;
ans+=d[T];
while(pre[T]!=S) {
T=pre[T];
if(use[T])cnt[item[T].col]--;
else cnt[item[T].col]++;
use[T]^=1;
}
return 1;
}
inline int intersection(const vector
int i;
n=ans=0;
tot=_tot;
for(i=0; i<pool.size(); i++) {
item[n++]=pool[i];
}
// for(i=0; i<pool.size(); i++)item[n++]=pool[i];
cnt.clear();
for(i=0; i<n; i++)use[i]=0;
for(i=0; i<tot; i++)if(!find())return -1;
return ans;
}
}
vector
bool chk(ll lm) {//finished
limit.clear();
int sum = 0;
for(auto it = E.begin(); it != E.end(); ++it) {
const int& w = it->first;
const vector<pair<int, int>>& v = it->second;
limit[w] = max(0LL, (ll)v.size() - lm / (ll)w);
sum += limit[w];
}
if(Matroid::intersection(edge_S,sum)!=-1)return 1;
else return 0;
}
int t;
void solve() {//finished
cin >> n >> m;
E.clear();
edge_S.clear();
ll r = 0;
for(int i = 1; i <= m; i++) {
int u , v , w;
cin >> u >> v >> w;
E[w].push_back(pair<int,int> {u , v});
r = max(r , (ll)(1LL
edge_S.push_back(Item(u,v,w,1));
// if(t54&&i1)cout<<u<<" "<<v<<" "<<w<<'\n';
}
ll l = 1;
while(l < r-1) {
ll md = ((l + r) >> 1);
if(chk(md)) {
r = md;
} else {
l = md+1;
}
}
if(chk(l))
cout << l << '\n';
else cout<<r<<'\n';
// cout<<n<<" "<<m<<'\n';
}
int main() {//finished
// freopen("01.in","rt",stdin);
// freopen("01.out","wt",stdout);
ios::sync_with_stdio(false) ;
cin.tie(0) ;
cout.tie(0);
cin >> t;
while(t--) {
solve();
}
cout<<clock();
return 0;
}
/
3
4 4
1 2 1
2 3 1
3 4 2
4 1 2
5 6
1 2 2
2 3 1
1 5 3
1 2 1
4 5 2
4 3 3
2 2
1 2 10
2 1 1
*/
'''