30098 - acm contest and blockout

为了准备将要举行的全国首届 ACM 学校竞赛，市长决定为所有的学校提供可靠的电力来源，他非常害怕停电。为了做到这一点，Future 电站一定要和一所学校（是哪一所学校并不重要）连接，而且，所有学校必须连接上电源。

本题设定，如果一所学校直接连接到 Future 电站，或者连接到任何其他有可靠的电力来源的学校，那么这所学校就有可靠的电力来源。本题给出在一些学校之间进行连接的成本。市长决定挑选出两个最便宜的连接方案——总的连接的成本等于学校之间的连接成本的总和。请帮助市长找到两个最便宜的连接方案。

输入首先在一行中给出测试用例的个数 T（1 < T < 15）。然后给出 T 个测试用例，每个测试用例的第一行给出两个整数 N 和 M，N（3 < N < 100）表示城市中学校的数目，M 表示学校之间可能的连接，用一个空格分开。

接下来 M 行每行给出 3 个整数 A_i、B_i、C_i，其中 C_i（1 < C_i < 300）是学校 A_i 和 B_i 之间连接的成本。学校用从 1 到 N 的整数来编号。

对每个测试用例输出一行，给出两个整数，表示两个最便宜的连接方案的成本，用一个空格分开。设 S_1 是最便宜的连接方案的成本，S_2 是次便宜的连接方案的成本。当且仅当有两个最便宜的连接方案时 S_1 = S_2；否则 S_1 < S_2。本题设定 S_1 和 S_2 是存在的。