Banikoara로 가는 가장 빠른 길

Codjo: Banikoara로 떠날 준비가 됐어.

Bossi: Parakou를 지나서 가자.

Assiba: 아니야, Banikoara로 가는 가장 빠른 길은 Djougou를 지나는 길이야.

도시 사이를 잇는 도로의 목록과 각 도로의 길이가 주어진다. 도시 A에서 도시 B까지 이동하는 최단 거리를 구하는 프로그램을 작성하라.

도로는 양방향이다. 입력에 적힌 도로 한 줄은 어느 방향으로도 지날 수 있다. 두 도시를 잇는 도로가 여러 개일 수 있고, 양 끝이 같은 도시인 도로가 있을 수도 있다.

첫째 줄에 데이터 집합의 개수 $P$ ($1 \le P \le 1000$)가 주어진다.

각 데이터 집합의 첫 줄에는 그 집합에 남은 줄의 수 $N$ ($1 \le N \le 500$), 공백, 출발 도시의 이름, 공백, 도착 도시의 이름이 주어진다. 이어지는 $N$개의 줄에는 도로가 하나씩 주어지며, 각 줄은 한쪽 도시의 이름, 공백, 다른 쪽 도시의 이름, 공백, 두 도시 사이의 거리(킬로미터)로 이루어진다.

거리는 $1$ 이상 $1000000$ 이하의 정수다. 도시 이름은 [a-z], [A-Z], 기호 "-"로 이루어진 길이 $30$ 이하의 문자열이며, 대문자와 소문자를 구분한다. 출발 도시에서 도착 도시로 가는 경로는 항상 존재한다.

각 데이터 집합마다 한 줄을 출력한다. 한 줄은 출발 도시의 이름, 공백, 도착 도시의 이름, 공백, 두 도시 사이의 최단 거리로 이루어진다.

출발 도시와 도착 도시가 같으면 최단 거리는 $0$이다.