Maximum Path Beauty in a Tree

You are given a tree of n cities connected by n - 1 bidirectional roads. Each road has a beauty index (a positive integer). Given two distinct cities A and B, your task is to compute the maximum beauty of the unique path between them. The beauty of a path is the sum of the beauty indices of all roads in that path. Since the answer can be very large, output it modulo \(10^9+7\).

Input Format: The first line contains three integers: n, A, and B. Each of the next n - 1 lines contains three integers u, v, and w representing a road between cities u and v with a beauty index w.

Output Format: Output a single integer: the maximum beauty of the path from city A to city B, modulo \(10^9+7\).

Note: The roads form a tree (i.e. a connected acyclic graph), ensuring a unique simple path between any two cities.

inputFormat

The input is given via standard input (stdin) with the following format:

n A B
u1 v1 w1
u2 v2 w2
... (n-1 lines in total)

Here, n is the number of cities, A and B are the two cities between which the path is considered, and each subsequent line represents a road connecting city u and city v with beauty w.

outputFormat

Output a single integer via standard output (stdout): the maximum beauty (sum of weights along the unique path from A to B) modulo \(10^9+7\).

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

15