题目描述

PDF
史云光:“卡拉研发中心。这是一个计算机研究实验室。Sunnydale的第三大雇员直到去年倒闭。什么，我有时不能有信息吗？”贾尔斯:“嗯，这是前所未有的。”阿什莉·盖博和托马斯·a·斯威登，《吸血鬼猎人巴菲》卡拉研发公司是一家大型高科技公司。他们手头有反垄断法，因为他们太大了。法官下令将该公司拆分为两个新公司A和B。Calax拥有一个连接多个城市的大型通信线路网络(每个城市都通过一条通信线路与其他城市相连)。他们现在需要将这些线路分成两组，A组和b组。这两组线路中的每一组仍能连接所有城市，这一点很重要，因为这两家公司不允许共享通信线路。还决定出售所有多余的线路，以保护两家新公司免受更多的反垄断诉讼。当然，这个操作的总成本需要尽可能的低。

输入格式

输入将包含许多案例。每个案例都以n开始，即城市的数量(最多10个)，然后是m，即通信线路的数量(最多25个)。接下来的m条线路将包含3个数字——由这条线路连接的两个城市以及保持这条线路的费用。每个城市将由[1，n]范围内的整数标识。一条线的成本最多1000。输入将由n为零的情况决定。

输出格式

每个测试用例单独在一行上输出一个整数——集合A和b中通信线路的最小总成本。打印No way！如果没有解决方案。

备注：

在第三个测试案例中，
一个可能的解决方案是让公司A保留这些通信线路:
1 2 10
1 3 10
1 4 10
1 5 20
让公司B保留这些线路:
1 4 20
2 3 20
3 4 20
4 5 30
总成本为 50 + 90 = 140。

样例 #1

样例输入 #1

2
3
1 2 10
2 1 20
1 2 30
3
3
1 2 10
1 2 20
2 3 50
5
8
1 2 10
1 3 10
1 4 10
1 4 20
1 5 20
2 3 20
3 4 20
4 5 30
0

样例输出 #1

30
No way!
140