Mutual Friends Finder

You are given a list of friend pairs together with the number of mutual friends between them. For each distinct user, your task is to determine the friend with whom they share the highest number of mutual friends. In case of a tie (i.e. multiple friends have the same maximum number of mutual friends), choose the one whose name is lexicographically smallest.

The input starts with an integer u representing the number of friend pairs. Each of the next u lines contains two usernames and an integer representing the mutual friend count between these users. Note that the relationships are bidirectional.

Your program should output, for every user found in the input, a line in the following format:

<username>: <friend> <count>

The output should be sorted in lexicographical order of the usernames.

Mathematical Formulation:

For each user x, let F(x) be the set of users that are friends with x together with a mutual friend count c(x, y) for each y in F(x). Your task is to find \[ y^* = \min_{\substack{y \in F(x)\\ c(x, y) = \max_{z \in F(x)} c(x, z)}} y \] and output the pair (y*, c(x, y*)) for each user x.

inputFormat

The first line contains a single integer u (1 ≤ u ≤ 10⁵), denoting the number of friend pairs.

Each of the next u lines contains two strings and one integer separated by spaces: user1 user2 count, where user1 and user2 are usernames (without spaces) and count (0 ≤ count ≤ 10⁹) is the number of mutual friends between them.

Note: The relationship is bidirectional so an entry user1 user2 count implies the same count for user2 and user1.

outputFormat

For each distinct user encountered in the input, output one line in the format:

username: friend count

where friend is the friend with the maximum number of mutual friends as defined above and count is that mutual friend count. The output must be sorted in lexicographical order of the username.

## sample

5
alice bob 10
alice charlie 15
bob charlie 5
diana bob 3
diana alice 2

alice: charlie 15
bob: alice 10
charlie: alice 15
diana: bob 3

</p>