#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
using namespace std;
#define int long long
#define P pair
#define pi P<int,int>
#define ff first
#define ss second
#define mp make_pair
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define V vector
#define vi V<int>
#define v2i V<vi>
#define v3i V<v2i>
#define vpi V<pi>
#define vb V<bool>
#define v2b V<vb>
#define pb push_back
#define S set
#define si S<int>
#define ins insert
#define era erase
#define M map
#define mii M<int,int>
#define Q queue
#define PQ priority_queue
const int MOD=998244353;
const int INF=1e9;
int smax(int& a, int b) {return a = max(a,b);}
int smin(int& a, int b) {return a = min(a,b);}

struct PFX {
	vector<int> pre;
	PFX(vector<int>& arr) {
		pre = vector<int>(arr.size()+1, 0);
		for (int i = 1; i <= arr.size(); i++) {
			pre[i] = pre[i-1] + arr[i-1];
		}
	}
	int RSQ(int l, int r) {
		if (l > r) return 0;
		return pre[r+1]-pre[l];
	}
};

int n, m, a, b, c;
V<vpi> adj;
V<vpi> rdj;
vi md;

void solve(int tv) {
	adj.clear();
	cin >> n >> m; adj = V<vpi>(n); rdj = V<vpi>(n); md = vi(n, INF);
	if (tv == 6) {
		cout << n << " " << m << "\n";
	}
	for (int i = 0; i < m; i++) {
		int u, v, w; cin >> u >> v >> w;
		if (tv == 6) {
			cout << u << " " << v << " " << w << "\n";
		}
		 --u; --v;
		if (u > v) {
			a = v; b = u; c = w;
		} else {
			adj[u].pb(mp(v,w));
			rdj[v].pb(mp(u,w));
			smin(md[v],w);
		}
	}
	if (tv == 6) cout << "\n\n";
	vi afg(n, INF);
	afg[0] = 0;
	for (int i = 1; i < n; i++) {
		afg[i] = md[i] + afg[i-1];
	}
	md[a] = 0;
	PFX ad(md);
	vi dp(n,INF); dp[0] = 0;
	for (int i = 1; i <= b; i++) {
		if (i == a) continue;
		for (auto e : rdj[i]) {
			if (e.ff == a) continue;
			smin(dp[i],dp[e.ff] + e.ss + ad.RSQ(e.ff+1,i-1));
		}
	}
	cout << min(afg[n-1],dp[b]+ad.RSQ(b+1,n-1)+c) << "\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	int t; cin >> t;
	for (int i = 0; i < t; i++) {
		solve(i);
	}
	return 0;
}