该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石老板的帝国日益强大，一共有 $n$ 座城市，其中 $1$ 号城市为首都，共有 $n-1$ 条道路形成一个树形结构。

石老板王国科技不发达，如果某个城市发生了事情要报告给在首都的石老板，只能靠传信员人工送往首都。

每个城市都有传信员，从一个城市出发通往首都的路上遇到中间的城市，可以选择更换传信员，或者让原来的传信员继续传信。每个传信员传信速度都是一样的，但是会根据距离不同而改变，传信员走 $L$ 距离需要 $L^2$ 时间，如果中途更换传递员，则需要 $P$ 时间来完成两个人的交接。

石老板想知道从任意一个城市出发给首都传信的最短时间的最大值是多少。

输入格式

第一行包含两个整数 $n,P$，表示城市数量和传信员交接时间。

接下来 $n-1$ 行，每行包含三个整数 $u,v,w$ ，表示城市 $u$ 与 $v$ 之间有一条长度为 $w$ 的双向边。

输出格式

输出从任意一个城市出发给首都传信的最短时间的最大值。

样例输入

4 5
1 2 1
1 3 2
3 4 3

样例输出

18

数据范围

对于 $30\%$ 的数据：$2\le n \le 5000$；

对于 $100\%$ 的数据：$2\le n \le 10^6$，$1\le P \le 10^6$,$1 \leq u,v \leq n, 1 \leq w \leq 100$。