题目描述

人生是一场旅程，我们走过的路充满曲折，有时会带我们到达意想不到的地方，遇见意想不到的人。如今，我们的西安之旅即将结束。以下问题需要仔细考虑。

几个月后，在青岛，一场重要的 ACM 竞赛已经安排好了。但在竞赛之前，我们需要去上海参加一场婚礼。竞赛结束后，我们将从上海离开中国，因此浦东国际机场（简称浦东）是我们旅程的终点。

我们有一些关键信息和必须完成的任务。

我们拥有一张 CNAC 的 VIP 卡。在每个机场，我们可以分别在出发层和到达层各享受一次特殊 VIP 服务。为了旅行的愉悦，缺少 VIP 服务是不可容忍的。也就是说，对于每个机场，我们只能从它离开一次，但从上海浦东出发、离开中国的最后一次航班不受此限制。同时，对于每个机场，我们只能到达它一次。

众所周知，上海有两个机场：虹桥机场（简称虹桥）和浦东机场。抵达其中一个再从另一个离开是不被允许的。但幸运的是，存在一项又好又坏的补偿服务。只要我们拥有一对往返于虹桥和浦东之间的转机记录，我们就可以获得一个合理的补偿。

实际上，我们在旅程中只考虑飞机，唯一的例外是在上海。例外之处在于，我们可以在上海的不同机场抵达和离开。但如果我们决定这么做，上述补偿是必需的。在我们的旅程结束前，我们会两次经过上海，一次为了婚礼，另一次为了最后的离开。如果我们想要获得补偿，第一次必须从浦东转机到虹桥，第二次则从虹桥转机到浦东。

其他城市机场之间的类似转机是不允许的。如果我们到达了一个城市，我们也不会通过汽车、公交或城际铁路前往相邻城市的机场。

现在，所有机场之间的可用航班已知。我们时间充裕，所以对飞行次数没有任何限制。我们需要的是整个旅程中航班总费用的最小值。

开始吧。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 160$），表示测试用例的总数。对于每个测试用例，第一行包含一个整数 $m$（$m \le 10000$），表示已知航班的数量。接下来的 $m$ 行，每行描述一个航班，包含两个字符串表示两个机场的名称，以及一个在 1 到 255 之间的整数表示费用。该航班连接两个给定的机场并且是双向的。每个机场的名称是一个仅由英文字母组成的非空字符串，长度不超过 10。我们用 “Xian” 表示西安唯一的机场，用 “Qingdao” 表示青岛唯一的机场。上海的机场分别用 “Hongqiao” 和 “Pudong” 描述。

输出格式

对于每个测试用例，输出最小的总费用，如果不可能则输出 $-1$。

3
4
Xian Hongqiao 3
Xian Pudong 4
Qingdao Hongqiao 4
Qingdao Pudong 3
4
Xian Hongqiao 4
Xian Pudong 3
Qingdao Hongqiao 3
Qingdao Pudong 4
6
Xian Hongqiao 4
Xian Pudong 3
Qingdao Hongqiao 3
Qingdao Pudong 4
Qingdao Xuzhou 1
Xuzhou Hongqiao 1

10
9
8

提示

翻译由 DeepSeek V4 Pro 完成