人生是一场旅途，我们走过的路蜿蜒曲折，有时会将我们带向意想不到的地方，遇见意想不到的人。现在，我们的西安之旅即将结束。我们需要仔细考虑以下问题。

几个月后，一场重要的 ACM 竞赛将在青岛举行。但在比赛之前，我们需要去上海参加一场婚礼。比赛结束后，我们将从上海离境，因此上海浦东国际机场（简称“浦东”）是我们旅程的终点。

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

我们拥有一张中国国际航空公司的贵宾卡。对于每个机场，我们可以在出发层和到达层分别享受一次特殊贵宾服务。为了旅行的愉悦，没有贵宾服务是无法忍受的。也就是说，对于每个机场，我们只能从中离开一次，但从上海浦东机场最后一次离境的情况除外。同时，对于每个机场，我们只能到达一次。

众所周知，上海有两个机场：虹桥机场（简称“虹桥”）和浦东。到达一个机场然后从另一个机场离开是不被允许的。但幸运的是，有一种既好又坏的补偿服务。通过在虹桥和浦东之间进行双向的转场记录，我们可以获得合理的补偿。实际上，在我们的旅程中，我们只考虑飞机，上海除外。例外情况是，我们可以在不同的机场到达和离开上海。然而，如果我们决定这样做，则必须进行上述的补偿。在旅程结束前，我们将两次经过上海，一次是为了婚礼，另一次是为了最终离境。如果我们想要获得补偿，第一次我们必须从浦东转场到虹桥，第二次我们将从虹桥转场到浦东。

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

现在，所有可用的机场间航班都已知。我们还有充足的时间。因此，我们对次数没有限制。我们需要的是整个旅程中航班的最小总成本。

开始吧。

输入格式

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

输出格式

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

样例

输入 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

输出 1

10
9
8