Agamemnon, the great king of Mycenae, was assembling his troops in Aulis to sail to the shores of Troy, when he had a vision of goddess Artemis. In this vision, Agamemnon found out that he had accidentally slain a deer that was sacred to Artemis, and now the goddess swore to make Agamemnon suffer on his voyage to Troy.

    Along his route to Troy, Agamemnon was planning to stop at the islands of Crete to gather resources for his formidable army. If Artemis were to find out about the sea routes Agamemnon took, she would use her powers to stop the wind along those routes, leaving Agamemnon and his crew stranded. As the trusty advisor of Agamemnon, you now have to help him devise a path between the islands of Crete that provides the army the maximum amount of resources, without letting Artemis discover the routes you take.

    The  islands of Crete are connected to each other via  sea routes. Along each route, Agamemnon can acquire a certain amount of resources. However, if a route is used more than  times, Artemis will detect the presence of Agamemnon along that route and stop the wind along that route. So, a feasible plan cannot use any route more than times. 

    Given that Agamemnon can start and end at any of the islands of Crete, come up with a feasible plan that maximises Agamemnon’s resource earnings. Note that Agamemnon can only collect resources along a sea route during its first use. He does not earn extra resources from a route on reusing it.

输入描述:

The first line of input will contain two integers,  and , the number of islandsof Crete, and the maximum number of times a single route may be used without being discovered by Artemis. Theislands of Crete are guaranteed to be connected by the sea routes.
    The following  lines describe the sea routes. Each line contains  integers each, , and , explaining that the sea route connects islands  and  and Agamemnon can acquire  units ofresources along this route. All sea routes are bidirectional, i.e. they can be used to travel from island  to , or fromisland  to .

输出描述:

Output a single value, the maximum amount of resources Agamemnon can acquire with a feasible plan, as described in the statement.

5 1
1 2 3
2 3 1
1 4 5
1 5 9

14

There are  islands in Crete, connected to each other via  routes, as shown in the figure: the first connecting island  and  and allowing Agamemnon to acquire  units of resources and so on. In this archipelago, the best plan forAgamemnon is to start at island , visit island  (acquiring  units of resources along the  route), and then endhis path at island  (acquiring another  units of resources along the  route), having earned a total of  units of resources. 

5 2
1 2 3
2 3 1
1 4 5
1 5 9

18