UVA10480 Sabotage

一个富裕的小型独裁政权突然被一场叛乱推翻。由于这一事件对世界经济造成了巨大动荡，一个帝国主义军事大国决定入侵该国并复辟旧政权。 为了圆满完成这次行动，必须彻底切断首都与最大城市之间的通信。这是一项艰巨的任务，因为该国所有城市都通过一个基于互联网协议的计算机网络相连——该协议允许消息通过网络中的任意路径传输。因此，必须将整个网络完全分割为两部分：首都在其中一部分，最大城市在另一部分，且两部分之间没有任何连接。 破坏不同通信线路的成本差异很大，因为有些线路比其他线路更容易接近。 城市 $1\sim n$ 编号，首都编号为 $1$，最大城市编号为 $2$。 请编写一个程序，给定网络结构和每条通信线路的破坏成本，确定需要切断哪些线路，才能以最低的总成本将首都与最大城市分隔开。

输入文件包含多组测试数据。每组数据的描述如下： 每组数据的第一行包含两个用空格分隔的整数：网络中的城市数量 $n$ 和通信线路的总数量 $m$。 接下来的 $m$ 行描述了所有的通信线路。每行包含三个用空格分隔的整数：前两个是该线路连接的两个城市的编号，第三个是切断这条线路的成本 $w$。任意一对城市在列表中最多出现一次。 输入以 $n$ 和 $m$ 均为 $0$ 的一组数据结束，这组数据不需要处理。

对于每组输入，你需要输出若干行。每组数据的输出描述如下： 输出所有需要切断的通信线路所连接的城市对（顺序任意），每行一对，两个城市编号间用空格分隔。如果存在多个解，输出任意一个即可。 每组测试数据的输出结束后，请输出一个空行。

$1\leq n\leq50,1\leq m\leq500,1\leq w\leq40000000$。