Earliest Cow to the Barn

Farmer John has rung the dinner bell so the cows, which are scattered in various pastures, start heading toward the barn. The pastures are labeled by characters. Pastures labeled with lowercase letters (a to z) do not have cows, whereas pastures labeled with uppercase letters (A to Y) each contain exactly one cow. The barn is always labeled Z and has no cow.

Each road connects two pastures (possibly the same pasture, and possibly with multiple roads between the same pair of pastures) and has an associated positive distance. It is guaranteed that at least one road leads to the barn, and every cow can reach the barn by following the shortest path. Since all cows travel at the same speed, the cow whose pasture has the shortest distance (via the shortest path) to the barn will be the first to arrive. There will be exactly one cow with the minimum travel distance.

Your task is to determine which cow (i.e. the label of the pasture with a cow) reaches the barn first.

Note: The letters m and M represent different pastures.

inputFormat

The first line contains an integer P representing the number of roads. Each of the following P lines contains two characters and an integer. The two characters represent the labels of the two pastures connected by that road, and the integer represents the distance between them. The two pastures are connected by an undirected road.

outputFormat

Output a single uppercase letter which is the label of the cow that reaches the barn first.

sample

3
A Z 10
b Z 3
A b 1

A