시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB0000.000%

문제

Kabul is a populated city. However, the public transportation has not grown at this stage. As a result, people at morning and evening have many problems to get to their destinations. The good things about this city is, you can reach to your destination using different routes. Every route has associated time, and price. One day, Toryalai has an urgent job to complete. He was in hurry and wanted to get to his destination as soon as possible. Your job is to help Toryalai to reach to his destination at minimum amount of time. Toryalai can go to his destination using many routes and routes can be formed by different intersections. Help him finding the best route to from provided routes his destination. Note: Toryalai cannot switch among routes.

입력

The first line is the number of test cases. Second line (R) contains number of routes Toryalai can use to reach destination. Then, R lines containing the routes associated times and prices. Starting from A as a start point and D as a destination. Maximum time Toryalai has is 12 hours and associated time for every route intersections has given to you in minutes.

Note:

There is no route exceeding the maximum time.

Every route reaches to destination.

출력

The time as Toryalai select the route with minimum associated time

예제 입력 1

1
2
A B 2 10Af, B C 5 40Af, C D 20 60Af
A F 1 40Af, F C 1 50Af, C D 20 30Af

예제 출력 1

22