题目描述

演员们雇了很多很多的学生来散发传单。每一个学生都负责一个公交车站。交通系统所有的线路都是单向的并且连接两个车站。

每半个小时，就会有一辆载有乘客的公交车从起点站出发。到达终点站之后，所有的公交车都会在空车的状态下返回那个等待了半个小时的车站，并且继续出发，例如从 $X:00$ 到 $X:30$，其中 $X$ 表示时间的小时部分。在两个车站之间来往的车票票价会在表格中给出，并且可以在并且可以在车站支付。交通路线经过精心设计，使得每一个环路（即起点和重点相同的路线）都会经过一个检查点（CCS）。

所有的学生志愿者们每天早上从 CCS 出发，所有人都会去预先定好的公交车站散发传单，车站数量和学生数量相等。

每天晚上，所有的学生坐车回到 CCS。你的任务是：编写一个程序，计算所有学生的交通费总和的最小值。

输入格式

第一行包含一个整数 $N$，代表数据的组数。

对于每组数据，第一行包含两个整数 $P$ 和 $Q$。$P$ 是包含 CCS 的线路数量，$Q$ 是公交线路的总数。

接下来有 $Q$ 行，每一行都包含三个整数 $u_i,v_i,w_i$，表示一条公交线路。

其中，$u_i$ 和 $v_i$ 分别表示公交的起始和终点站，$w_i$ 表示这条公交线路的票价，CCS 的代表数字是 $1$。

输出格式

对于每一组数据，输出一行表示所有学生的交通费总和的最小值。

数据范围与约定

$1 \le P,Q \le 10 ^ 6, \sum w_i \le 10 ^ 9$。

数据保证任意两个车站之间有至少一条路线可以互相到达。