课程设计题目急求思路与答案问题描述。灰太狼希望能利用它们抓住羊村里所有的羊，所以现在需要制定一个完美的计划。灰太狼已经获

课程设计题目急求思路与答案
问题描述。灰太狼希望能利用它们抓住羊村里所有的羊，所以现在需要制定一个完美的计划。灰太狼已经获取了羊村的地图。他发现羊村由N个交叉路口和N-1条双向街道构成，而且无论从哪个交叉路口出发沿着街道走都能到达其它的任何一个交叉路口。每条街道上都有房子，每个房子中都住着羊。为了保证计划万无一失，灰太狼选择在半夜行动，因为这时所有的羊都会在自己的房子中睡觉。灰太狼计划将他制造出的K个机器人放在某个交叉路口处，机器人会沿着街道行走，并且可以在任何一个交叉路口停下，不同的机器人可以停在不同的位置。因为捉羊机器人的性能非常优秀，所以每条街道只要被一个机器人走过一次，这条街道上住着的所有羊就都会被捉住。当所有的羊都被抓住后，灰太狼的计划就成功了。机器人在街道上移动需要耗费非常多的能量。为了节约能源，灰太狼迫切想要知道所有机器人的移动路线长度之和的最小值。 输入格式输入文件包含N行。第1行包含两个正整数N、K，分别表示交叉路口的总数和机器人的个数。交叉路口的序号为1到N。第2行到第N行，每行包含三个用空格隔开的正整数A、B、C，表示有一条连接交叉路口A和交叉路口B的街道，且该街道的长度为C。输出格式输出文件包含N行，每行一个正整数，其中第i行的整数表示如果所有的机器人从序号为i的交叉路口出发，那么移动路线的长度之和最小是多少。输入样例 5 3 1 2 7 2 3 5 3 4 14 3 5 8 输出样例 42 39 34 42 42 样例说明 若所有的机器人从1号路口出发，那么最优路线为： 1号机器人：1→2→3→5→3→4，长度为42。 2号机器人：停留在出发点。 3号机器人：停留在出发点。总长度为42。若所有的机器人从2号路口出发，那么最优路线为： 1号机器人：2→1，长度为7。 2号机器人：2→3→4，长度为19。 3号机器人：2→3→5，长度为13。总长度为39。若所有的机器人从3号路口出发，那么最优路线为： 1号机器人：3→2→1，长度为12。 2号机器人：3→4，长度为14。 3号机器人：3→5，长度为8。总长度为34。数据范围对于10%的数据，N≤10，K≤2。对于20%的数据，N≤100，K≤6。对于35%的数据，N≤200，K≤12。对于50%的数据，N≤500，K≤18。对于65%的数据，N≤8000，K≤25。对于另外20%的数据，N≤15000，K≤2。对于全部的数据，N≤15000，K≤30。每条街道的长度都不超过100。