题目描述

在电视时代，观看剧院演出的人并不多。马利迪尼西亚的古喜剧演员们深知这一点。他们想要推广戏剧，尤其是古喜剧。为此，他们印制了包含所有必要信息和节目单的邀请卡，并雇佣了许多学生志愿者在人群中分发这些邀请卡。每位学生志愿者被分配到一个特定的公交站点，全天驻守并向乘坐公交的乘客发放邀请。学生们还参加了一个特殊课程，学习如何影响他人，以及区分影响和抢劫。

该城市的交通系统非常特殊：

1. 所有公交线路都是单向的，且仅连接两个站点
2. 公交车每半小时从始发站载客出发一次
3. 到达终点站后，空车返回始发站，等待下一个整点或半点（如$X:00$或$X:30$，$X$表示小时数）
4. 站点间的票价由特殊表格规定，需现场支付
5. 所有环线（即起点和终点相同的路线）都会经过中央检查站（CCS），每位乘客必须在此接受包括身体扫描在内的严格检查

所有ACM学生成员每天早晨从CCS出发。每位志愿者需要前往一个预定的站点邀请乘客，志愿者数量与站点数量相同。傍晚时分，所有学生都要返回CCS。你需要编写一个计算机程序，帮助ACM最小化每日需要支付的员工交通费用。

输入格式

输入包含$N$个测试用例。第一行仅包含正整数$N$。随后是各测试用例：

• 每个用例的第一行包含两个整数$P$和$Q$（$1 \leq P,Q \leq 1000000$），其中$P$表示包含CCS在内的站点总数，$Q$表示公交线路数量
• 接下来$Q$行，每行描述一条公交线路，包含三个数字：始发站、终点站和票价
• CCS的编号为$1$
• 票价为正整数，总和小于$1000000000$
• 题目保证任意两个站点之间均可互相到达

输出格式

对于每个测试用例，输出一行，表示ACM每日需要支付的最小交通费用。

输入样例

2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

输出样例

46
210

题目来源

$1998$年中欧地区竞赛