题目描述

Olympiland 有 N 个城镇，编号为 1 到 N。道路网络满足：任意两城镇之间都恰好存在一条简单路径。也就是说，这个道路网络是一棵树。

政府列出了一批运输路线。每条路线由三个量 (u,v,p) 描述：

• 设备需要在城镇 u 和 v 之间运输；
• 无论具体方向如何，承接这条运输路线都能获得利润 p。

你经营一家运输公司。比赛规则是：你可以先任选两个城镇 x,y，然后你的公司将承接所有起点和终点都落在路径 x~y 上的运输路线（包含端点）。

请你选择两个城镇，使总利润最大，并输出这两个城镇以及最大利润。

输入格式

第一行输入一个正整数 N，表示城镇数。

接下来 N-1 行，每行两个不同的正整数，表示一条道路连接的两个城镇。

接下来一行输入一个正整数 M，表示运输路线数量。

再接下来 M 行，每行三个正整数：两端城镇编号以及该路线带来的利润。

输出格式

输出三个整数：两个被选中的城镇编号，以及能取得的最大利润。

如果最优解不唯一，输出任意一组即可。

数据范围

• 2 <= N <= 10^5
• 0 <= M <= 10^5
• 1 <= 每条路线利润 <= 10^3
• 20% 的测试中：N < 100
• 40% 的测试中：N < 1000
• 70% 的测试中：存在一条最优路径，且它包含输入道路表中的第一条边

样例

输入

6
1 2
2 3
2 4
5 4
6 4
4
1 4 10
2 5 20
6 3 15
2 1 1

输出

5 1 31