（（（

真 wa 了 qwq

90pts

又臭又长的 dij

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ul unsigned long long

using namespace std;

map<string, int> mp;

struct Edge {
	int to, nxt, dis;
}e[1919810];
int cnt;
int hd[1919810];
int dis[1919810];
struct Node {
	int x, dis;
	bool operator < (const Node& p) const {
		return dis > p.dis;
	}
};

priority_queue<Node> q;

void add_edge(int u, int v, int d) {
	++cnt;
	e[cnt].to = v;
	e[cnt].nxt = hd[u];
	e[cnt].dis = d;
	hd[u] = cnt;
}

void Dijkstra(int s) {
	Node al, be;
	al.x = s;
	al.dis = 0;
	dis[s] = 0;
	q.push(al);
	while (!q.empty()) {
		be = q.top();
		q.pop();
		int u, v, d;
		u = be.x;
		for (int i = hd[u]; i; i = e[i].nxt) {
			v = e[i].to;
			d = e[i].dis + be.dis;
			if (d < dis[v]) {
				dis[v] = d;
				al.x = v; al.dis = d;
				q.push(al);
			}
		}
	}
}

void Solv() {
	int n, m, d;
	n = 0;
	scanf ("%d", &m);
	for (int i = 1; i <= m; ++i) {
		string a, b;
		int u, v;
		cin >> a >> b >> d;
		if (!mp[a]) mp[a] = u = ++n;
		else u = mp[a];
		if (!mp[b]) mp[b] = v = ++n;
		else v = mp[b];
		add_edge(u, v, d);
		add_edge(v, u, d);
	}
	string a, b;
	cin >> a >> b;
	int s, t;
	s = mp[a]; t = mp[b];
	for (int i = 0; i <= 10000; ++i) dis[i] = 0x7fffffff;
	Dijkstra(s);
	if (dis[t] != 0x7fffffff) cout << dis[t] << endl;
    else cout << -1 << endl;
	mp.erase(mp.begin(), mp.end());
	for (int i = 1; i <= cnt; ++i) e[i] = (Edge){0, 0, 0};
	cnt = 0;
	for (int i = 1; i <= 10000; ++i) hd[i] = 0;
}

int main() {
	int T;
	scanf ("%d", &T);
	while (T--) Solv();
}