SP239 BTOUR - Tour de Byteland

比特兰的市长任期将近尾声，为了连任，他开始了准备。这是他40年政治生涯中第一次感觉到胜算不太确定。一个民意调查的结果显示，超过90%的市民认为市长形象不佳，认为他体态笨重、烟瘾缠身、总是整天躺在椅子里打盹。 经过与公关团队的深入探讨，市长决定重新塑造自己的形象。他计划组织、赞助并参加比特兰的首届自行车比赛！显然，比赛的关键在于媒体对市长的正面报道，其他方面能省则省。比特兰的街道图由双向街道段连接形成，但交叉口最多只有4条街道相交。骑手们将在一个简单的环形赛道上骑行，这条封闭的赛道由若干街道组成，每圈中骑手只能沿一条街走一遍，并在每个交叉口仅经过一次。由于几个显而易见的原因，市长想要选择总路程最短的比赛路线。请助市长找出这样的环路的长度，并告诉他在组织比赛时，可选择多少种长度相同的最短环路。

输入的第一行包含一个整数 $t \le 200$，表示测试用例的数量。随后是 $t$ 个测试用例。 每个测试用例第一行包含两个整数 $n$ 和 $m$，表示比特兰有多少个交叉口和街道（$1 \le n \le 1000$）。紧接着 $m$ 行中，每行有三个整数 $u_i, v_i, d_i$，代表第 $i$ 条街道的起点、终点和长度（$1 \le u_i \le v_i \le n, 1 \le d_i \le 10^6$）。

对每个测试用例，输出一行，包含两个非负整数 $d$ 和 $c$，分别代表最短环路的长度和这种环路在图中出现的数量。如果无法形成环路，输出 `0 0`。 **本翻译由 AI 自动生成**