{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"在电视时代,很少有人参加戏剧表演。马里迪尼西亚古董喜剧演员们意识到了这一事实。他们希望传播戏剧,尤其是古董喜剧。他们印制了带有所有必要信息和节目单的邀请卡。许多学生被雇佣来向人们分发这些邀请。每位学生志愿者都被分配了一个公交车站,并在那里整天待着,向乘坐公交车的人们发放邀请。学生们接受了一门特殊课程,在课程中他们学会了如何影响人们,以及影响和抢劫之间的区别。\u003cbr\u003e\u003cbr\u003e交通系统非常特殊:所有线路都是单向的,连接着两个车站。公交车每隔半小时从出发站点出发,上车乘客。到达目的地后,它们空车返回到出发站点,在那里等待下一个整点或半点,例如 X:00 或 X:30,其中 \u0027X\u0027 表示小时。两个站点之间的交通费由特殊表格给出,并在现场支付。线路的规划是这样的,每个往返行程(即从同一站点出发并到达同一站点的旅程)都会经过一个中央检查站(CCS),乘客必须在那里接受彻底检查,包括全身扫描。\u003cbr\u003e\u003cbr\u003e所有ACM学生成员每天早晨都离开CCS。每位志愿者都要前往一个预定的站点邀请乘客。志愿者的数量与站点数量相同。一天结束时,所有学生都会返回CCS。你需要编写一个计算机程序,帮助ACM最大程度地减少每天为员工交通费用支付的金额。"}},{"title":"输入","value":{"format":"HTML","content":"输入包含N个案例。输入的第一行仅包含一个正整数N。然后是案例。每个案例以包含两个整数P和Q的一行开始,其中 1 \u0026lt;\u003d P,Q \u0026lt;\u003d 1000000。P是包括CCS在内的站点数量,Q是公交线路数量。然后是Q行,每行描述一条公交线路。每行包含三个数字 - 出发站点、目的站点和价格。CCS由编号1指定。价格是正整数,其总和小于1000000000。你也可以假设从任何站点到任何其他站点都是可能的。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个案例,输出一行,包含ACM每天为其志愿者的交通费用支付的最小金额。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n2 2\r\n1 2 13\r\n2 1 33\r\n4 6\r\n1 2 10\r\n2 1 60\r\n1 3 20\r\n3 4 10\r\n2 4 5\r\n4 1 50\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e46\r\n210\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}