#include #include #include #include #include using namespace std; const int INF = INT_MAX; struct Edge { int to; int time; Edge(int t, int w) : to(t), time(w) {} }; struct Node { int station; int state; //0没用过,1用过了 int time; Node(int s, int st, int t) : station(s), state(st), time(t) {} bool operator>(const Node& other) const { return time > other.time; } }; int main() { int n, s, t; while (cin >> n >> s >> t) { int m; cin >> m; vector> bus(n + 1); for (int i = 0; i < m; i++) { int a, b, c; cin >> a >> b >> c; bus[a].push_back(Edge(b, c)); bus[b].push_back(Edge(a, c)); } int k; cin >> k; vector> metro(n + 1); for (int i = 0; i < k; i++) { int x, y, z; cin >> x >> y >> z; metro[x].push_back(Edge(y, z)); metro[y].push_back(Edge(x, z)); } vector> dp(n + 1, vector(2, INF)); //换乘点K vector K_record(n + 1, INF); priority_queue, greater> pq; dp[s][0] = 0; pq.push(Node(s, 0, 0)); while (!pq.empty()) { Node curr = pq.top(); pq.pop(); int u = curr.station; int state = curr.state; int time = curr.time; if (time > dp[u][state]) { continue; } for (const Edge& e : bus[u]) { int v = e.to; int new_time = time + e.time; if (new_time < dp[v][state]) { dp[v][state] = new_time; if (state == 1 && K_record[u] != INF) { K_record[v] = K_record[u]; } pq.push(Node(v, state, new_time)); } else if (new_time == dp[v][state] && state == 1 && K_record[u] != INF) { if (K_record[v] == INF) { K_record[v] = K_record[u]; } else { K_record[v] = min(K_record[v], K_record[u]); } } } if (state == 0) { for (const Edge& e : metro[u]) { int v = e.to; int new_time = time + e.time; if (new_time < dp[v][1]) { dp[v][1] = new_time; K_record[v] = u; pq.push(Node(v, 1, new_time)); } else if (new_time == dp[v][1]) { K_record[v] = min(K_record[v], u); } } } } int T = min(dp[t][0], dp[t][1]); cout << T << endl; if (dp[t][0] <= dp[t][1]) { cout << "no metro" << endl; } else { cout << K_record[t] << endl; } } return 0; }