Problem Description

Patrik and Josip are riding a tram. They have traveled through \( n \) stations.

At each station except the first one, one of the following events occurs:

• Patrik says: It has been \( t \) minutes since we got on the tram.

• Josip says: It took \( t \) minutes to travel from station \( y \) to here.

Given this information, you are asked to determine the shortest time required between any two stations, and identify the starting and ending stations for this shortest time.

Input Format

The input consists of \( n \) lines:

The first line contains an integer \( n \) (\( 2 \le n \le 1000 \)), representing the number of stations.

The next \( n-1 \) lines describe the events at each station from the second to the \( n \)-th station:

• The first type of operation: Patrik t_i (\( 1 \le t_i \le 10^9 \))

• The second type of operation: Josip y_i t_i (\( y_i < i + 1 \), \( 1 \le t_i \le 10^9 \))

Each station is located at a different position.

Output Format

Output a single line containing three integers \( t \), \( x_1 \), and \( x_2 \), representing the shortest time, and the starting and ending stations for this shortest time.

If there are multiple solutions, output the one with the smallest lexicographical order.

Sample Input and Output

Sample Input #1

4
Patrik 3
Patrik 5
Josip 1 7

Sample Output #1

2 2 3

Sample Input #2

2
Josip 1 5

Sample Output #2

5 1 2

Sample Input #3

5
Patrik 4
Josip 2 4
Josip 2 6
Josip 4 2

Sample Output #3

2 3 4

Notes

This problem is bundled with subtasks.

The total score for this problem is 50 points.

见题面 Input 部分

见题面 Output 部分