None国没有“高考”，上大学靠关系！Boss Liu想通过“关系”让孩子进入最好的University of None（校长是Mr. None）。Boss Liu的关系网络中有N个人，其中包含Boss Liu以及Mr. None。Boss Liu的关系网络是赤裸裸的金钱关系网络，这意味着两个人之间如果有关系，会相互帮忙，但帮忙都是要收费的! Boss Liu可以求A帮忙，A求B帮忙，B求C帮忙,…,如果最终求到校长那里，Boss Liu的儿子会被顺利录取，当然所有的费用都得有Boss Liu支付。 你讨厌Boss Liu，想破坏Boss Liu的计划。你所能做的就是说服老板刘的关系网中的某个人拒绝任何帮忙要求。这个人可以是任何人，但不能是Boss Liu或校长。如果你不能让Boss Liu失败，你希望Boss Liu花尽可能多的钱。你应该知道，在你尽了最大努力后，老板刘必须花多少钱才能得到他想要的东西。请注意，如果你什么都不做，Boss Liu肯定会成功。 输入格式: 第一行包含两个整数n和m，n为关系网中的人数。 编号从1至n，刘老板是第1位，校长是第n位。M表示刘老板的关系网中有M个关系。（3 <n= 30, 3＜＝m <＝1000） 接下来有m行。每行包含三个整数A、B和C，意思是A和B之间存在关系，如果A向B或B向A求助，刘老板将支付C元。 输出格式: 在你尽了最大努力后，输出Boss Liu要花的最少的钱。如果Boss Liu不能把他的孩子送到大学，就打印“Fail”。

对于此问题，可以使用最小生成树算法来解决。具体来说，可以使用 Kruskal 算法，它的时间复杂度为 O(mlogm)，其中 m 为边数。下面是具体的步骤：

1. 对于每条边，按照边权从小到大排序。
2. 依次遍历每条边，如果这条边连接的两个点不在同一个连通块中，就将这条边加入最小生成树中，并将这两个点合并到同一个连通块中。
3. 最后如果最小生成树中连接了 1 号点和 n 号点，输出最小生成树的总权值，否则输出 "Fail"。

具体的代码实现如下：