Invitation Cards

翻译： 描述 在电视时代，没有多少人参加戏剧表演。 Malidinesia古董喜剧演员知道这个事实。他们想传播戏剧，最重要的是古董喜剧。他们已经印制了包含所有必要信息和程序的邀请卡。许多学生被聘请将这些邀请分发给人们。每个学生志愿者都分配了一个公交车站，并且他或她在那里呆了一整天，并邀请乘坐公共汽车的人。学生学会了如何影响人们以及影响和抢劫的区别。 运输系统非常特殊：所有线路都是单向的，并且连接两个站点。公共汽车每半小时就与旅客一起离开始发站。到达目的地站点后，它们返回到原始站点，在那里等待直到下一个半小时，例如， X：00或X：30，其中'X'表示小时。两站之间的运输费用由特别表格支付，并在现场支付。线路的设计方式是每次往返（即在同一站点开始和结束的旅程）通过中央检查站（CCS），每个乘客必须通过包括全身扫描在内的全面检查。 所有的ACM学生成员每天早上离开CCS。每位志愿者都将前往一个预定的站点邀请乘客。志愿者的数量和站点一样多。在一天结束时，所有学生都会回到CCS。您需要编写一个计算机程序，帮助ACM减少每天为其员工的运输支付的金额。 输入 输入由N个案例组成。输入的第一行仅包含正整数N.然后遵循这些情况。每种情况都从一行包含恰好两个整数P和Q的行开始，1 <= P，Q <= 1000000。P是包括CCS的停止点的数量，Q是总线的数量。然后有Q行，每行描述一条总线。每一行都包含三个数字 - 原始站台，目的站台和价格。 CCS用编号1表示。价格是总和小于1000000000的正整数。您也可以假定始终可以从任何站点到任何其他站点。 输出 对于每一种情况，请打印一行，其中包含ACM每天要支付的最低金额，用于志愿者的差旅费用。 翻译提供者：威慑

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=9&page=show_problem&problem=662 [PDF](https://uva.onlinejudge.org/external/7/p721.pdf) 



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