U119268 搞搞新意思（gao）

一天，oscar 得到了 $n$ 个点 $n-1$ 条边的无向连通图。这个图的每条边有一个非负整数作为边权。可以证明，对于任意两个点，有且仅有一条路径连接它们。我们定义两个点之间的距离为连接它们的路径上的边的边权总和。定义直径为所有点两两之间距离的最大值。 现在，oscar 想在这棵树上搞搞新意思。他会进行很多次操作，每次，他会让他的仓鼠们告诉他一个非负整数，然后他会把图中的一条边的边权改成这个数（如果他愿意的话也可以不做改动），使得直径最小，你需要求出这个最小的直径。每次操作后他都会把图复原。

无

无

对于20%的数据，$n,m\le 200$ 对于40%的数据，$n,m\le 2000$ 对于另20%的数据，$n\le 10^5, m\le 10$ 对于100%的数据，$1\le n,m\le 10^5, 1\le w\le 10^9$