Traveling Salesman Problem: Minimum Round Trip Time

You are given an undirected weighted graph representing cities and the travel time between them. Given a starting city, your task is to compute the minimum time required to start at the given city, visit every other city exactly once, and return to the starting city.

The input begins with the starting city's name, followed by the number of routes available. Each subsequent line describes a bidirectional route between two cities along with the travel time. The travel time between any two connected cities is a positive integer.

The answer is the minimal total time of completing such a round trip. Formally, if we denote a tour by a permutation \( \pi \) of the cities (excluding the starting city), the total time is:

$$T = d(\text{start}, \pi(1)) + \sum_{i=1}^{n-1} d(\pi(i), \pi(i+1)) + d(\pi(n), \text{start}), $$

where \(d(a, b)\) is the travel time between cities \(a\) and \(b\). Your program should compute the minimum \(T\) over all possible permutations.

Note: It is guaranteed that a circuit exists that visits all cities.

inputFormat

The input is read from standard input and has the following format:

• The first line contains a string representing the starting city.
• The second line contains an integer \(N\) (\(N \ge 1\)) denoting the number of routes.
• The next \(N\) lines each contain two strings and an integer, separated by spaces, representing a bidirectional route between two cities and the travel time between them.

For example:

A
6
A B 4
A C 2
A D 5
B C 1
B D 3
C D 6

outputFormat

Output a single integer: the minimum travel time required to start from the given city, visit all other cities exactly once, and return to the starting city. The output should be written to standard output.

## sample

A
6
A B 4
A C 2
A D 5
B C 1
B D 3
C D 6

11

</p>