U184835 《Valiant Hearts：The Great War》

 ### (May there be no more war in the world) ###### Dearest Marie: ##### As the war ends for me,I have no regrets,I’ve seen too much horror.I hope fate has been more merciful to you. ###### Our time on Earth is brief,and mine has been filled with so much joy,that I can only be thankful for how much i’ve been blessed,most specially for the wonder you brought into my life. ###### This letter is my last,I’ve been found guilty by a military court for the death of an officer.It was not my intention to kill him. #### War makes men mad. ###### Though I failed Karl,I know my sacrifice has not been in vain.I fought for my country and my liberty,and my honour is assured.Since it is the will of God to separate us on Earth,I hope we’ll meet again in heaven.Keep me in your prayers. ###### Your loving papa, ###### Always.

1917年 第一次世界大战 维米岭 英属加拿大部队 弗莱迪作为美国的志愿军加入了战斗。 通过前线勘察地形，朱利安·宾将军发现虽然德军步兵集团（疑似是拜伦伯爵的军队）在固守碉堡时有多种组合，但是基本就三种基本的形式。 德国的碉堡有的需要乔治驾驶侦察机去勘察才可以发现弱点，但是有可能会被戈林驾驶的战斗机击落。 有的碉堡则需要手里拿着手榴弹的英国某团长带领着士兵去冲锋才有可能找到该碉堡的弱点，显然这样损失会很大。 有的碉堡则需要找到由阿米尔卡雷带领的狙击队所在的狙击塔，这肯定也要要派英国某团长去侦察，而且肯定也会造成巨大损失。 ~~（一个小胡子骑着自行车闪过）~~ 对于以上的方案朱利安·宾将军肯定不满意（拜伦伯爵狂喜） 为了更好的取得胜利，朱利安·宾将军要求弗莱迪用一种更好的办法去发现这三种防御形式的弱点，所以朱利安·宾将军把德军碉堡的情报给了你（碉堡是由n各点和n-1条边组成） 可是弗莱迪不会呀，他只会在战场上冲锋 ~~况且人家不会计算机~~ 再加上夏尔将军和图帅被关进了战俘营，他就更加不回了。 ~~就大林在西伯利亚捕鱼~~ 他只好来请教你这位 one of the best （待机四个任期的【虽然还没值完班】） 的***********

输入一个整数$n$表示询问的次数 在输入一个整数$m$表示碉堡的种类 if $m$=1 输入，包含三个整数 $a_{i},b_{i},c_{i}$ ，表示点 $a_{i} 和 b_{i} $ 之间存在一条权值为 $c_{i}$ 的边。 要求求出碉堡（树）最长路径的长度，即：输出一个整数，表示树（碉堡）的最长距离的长度。 if $m$==2 输入，包含三个整数 $a_{i},b_{i},c_{i}$ ，表示点 $a_{i} 和 b_{i} $ 之间存在一条权值为 $c_{i}$ 的边。 要求找到一个点，使得该点到碉堡（树）中其他点的最远距离最近，即：输出一个整数，表示树（碉堡）的中心到树（碉堡）中其它点的最远距离。 if $m$==3 输入，包含两个整数 $a_{i},b_{i}$ ，表示点 $a_{i} 和 b_{i} $ 之间存在一条边。 要求求出删掉一个点之后，剩余各个连通块中点数的最大值最小，即：输出一个整数，表示将重心删除后，剩余各个连通块中点数的最大值。

输出$n$行整数，每行一个整数表示上述要求要输出的结果。

数据范围： $1≤n≤10000$ 1≤$a_{i}$,$b_{i}$≤n, $−10^{5}$≤$c_{i}$≤$10^{5}$