Tram

Interview

Time limit1sMemory limit1024 MB

Summary

Given each station's time from station 1 (Patrik) or from an earlier station (Josip), find the pair of stations with the smallest time gap.

Level: Easy3 of 10
Topics: Sorting, Array
Solved: No attempts yet

Problem

One magical night, Patrik and Josip were talking about the number 42 and the meaning of life. They were interrupted by the famous lady voice in the tram: The next stop is Jordanovac. Patrik and Josip were distracted by this common sentence and started discussing:

Patrik: It is a very short ride between Joranovac and Maksimir, isn't it?

Josip: It is, but the ride between Mašićeva and Kvatrić is way shorter.

Patrik: Really? I disagree.

Josip: I wonder, which is the shortest ride between all stations?

Paula, a big public transport vehicle, was listening carefully to their conversation. The problem of finding the shortest ride interested her so much that she stayed in the tram longer than she intended.

At each station (except the first one, where they entered the tram), one of the following two things happened:

Patrik said: t minutes have passed since we entered the tram.
Josip said: From station y to this station, t minutes have passed.

But before Paula could hear their conclusion about the shortest ride, they left the tram! Luckily, Paula remembers all their statements. Help her find the duration of the shortest ride and the two stations between which the tram drove on that ride.

Input

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

The i-th of the following $n - 1$ lines contains information about station $i + 1$ in one of the following formats:

Patrik $t_i$ : The duration of the ride between station 1 and station $i + 1$ is $t_i$ ( $1 \le t_i \le 10^9$ ).
Josip $y_i$ $t_i$ : The duration of the ride between station $y_i$ and station $i + 1$ is $t_i$ ( $y_i < i + 1$ , $1 \le t_i \le 10^9$ ).

Every station is in a distinct position.

Output

Output one line with three numbers: $t$ , $x_1$ , and $x_2$ . Here $t$ is the duration of the shortest ride, and $x_1$ and $x_2$ are the indices of the starting and ending stations of that ride.

If multiple solutions exist, print the one with the smallest station indices.

Hint

Clarification of the first example: The tram drove for 3 minutes from the first to the second station, and 5 minutes from the first to the third. So the ride from the second to the third station took 2 minutes, which is the shortest ride.

Clarification of the third example: The ride between the fourth and fifth stations is also 2 minutes, but because they have greater indices, only the 2 3 4 solution is accepted.

Examples3

Example 1
Input
```
4
Patrik 3
Patrik 5
Josip 1 7
```
Expected output
```
2 2 3
```
Example 2
Input
```
2
Josip 1 5
```
Expected output
```
5 1 2
```

Example 3

Input

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

Expected output

2 3 4