#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <map>#include <string>using namespace std;int N, idx;int dp[2][205][205];map<string, int>mp;void floyd() { for (int k = 0; k < idx; ++k) { for (int i = 0; i < idx; ++i) { if (dp[0][i][k] == -1 || i == k) continue; for (int j = 0; j < idx; ++j) { if (dp[0][k][j] == -1 || j == k) continue; if (dp[0][i][j] == -1) { dp[0][i][j] = dp[0][i][k] + dp[0][k][j]; } else if (dp[0][i][j] > dp[0][i][k] + dp[0][k][j]) { dp[0][i][j] = dp[0][i][k] + dp[0][k][j]; } } } } for (int k = 0; k < idx; ++k) { for (int i = 0; i < idx; ++i) { if (dp[0][i][k] == -1 || i == k) continue; for (int j = 0; j < idx; ++j) { if (dp[0][k][j] == -1 || j == k) continue; if (dp[0][i][j] == -1) continue; if (dp[1][i][k] != -1) { if (dp[1][i][j] == -1) { dp[1][i][j] = dp[1][i][k] + dp[0][k][j]; } else { dp[1][i][j] = min(dp[1][i][j], dp[1][i][k] + dp[0][k][j]); } } if (dp[1][k][j] != -1) { if (dp[1][i][j] == -1) { dp[1][i][j] = dp[0][i][k] + dp[1][k][j]; } else { dp[1][i][j] = min(dp[1][i][j], dp[0][i][k] + dp[1][k][j]); } } } } }}int main() { string a, b, sta, end; int ct; while (cin >> sta >> end) { memset(dp, 0xff, sizeof (dp)); idx = 0; mp.clear(); cin >> N; for (int i = 0; i < N; ++i) { cin >> a >> b >> ct; if (mp.count(a) == 0) { mp[a] = idx++; } if (mp.count(b) == 0) { mp[b] = idx++; } dp[0][mp[a]][mp[b]] = ct; dp[1][mp[a]][mp[b]] = 0; } floyd(); printf("%dn", dp[1][mp[sta]][mp[end]]); } return 0;}
