Migrated from Lutece 2172 魔法松鼠

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

大魔法师eom在寻找他丢失的松鼠。这只松鼠藏在一棵树上的某个节点，但是eom不知道它藏在什么地方。作为一个魔法师，eom能在一个节点放出许多魔法生物向不同的方向以1的速度前进寻找他的松鼠，他还能使用一次魔咒把树上某两个相邻节点之间的距离变为0。请你帮助他找到一个位置，使得最坏的情况下，他从该位置释放魔法生物开始寻找也能最快找到他的松鼠。

Input

第一行有1个整数$n$，表示这棵树有$n$个节点。

接下来$n-1$行每行$3$个整数$u$，$v$，$w$，表示结点$u$，$v$由一条长度为$w$的边相连。

Output

输出最坏情况下能最快找到松鼠的节点编号与时间，如果答案有多个，要求节点编号字典序最小。

Samples

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

1 2

Constraints

$n \leq 2\times 10^6$

$w \leq 200$

Resources

2019 UESTC ACM Training for Dynamic Programming