#include <iostream>#include <cstdlib>#include <cstring>#include <cstdio>#include <queue>using namespace std;const int INF = 0x3f3f3f3f;int N, M, K;struct Edge { int v, ct, next;}e[1005], re[1005];int idx, ridx, head[1005], rhead[1005];int path[1005];int dis[1005][1005];int rdis[1005][1005];bool vis[1005];void insert(int a, int b, int ct, Edge e[], int head[], int &idx) { ++idx; e[idx].v = b, e[idx].ct = ct; e[idx].next = head[a]; head[a] = idx;}void spfa(int sta, int dis[], Edge e[], int head[], int fn) { if (fn == 1) { memset(dis, 0, sizeof (int) * 1005); } else { memset(dis, 0x3f, sizeof (int) * 1005); } memset(vis, 0, sizeof (vis)); queue<int>q; dis[sta] = 0; vis[sta] = true; q.push(sta); while (!q.empty()) { int v = q.front(); q.pop(); vis[v] = false; for (int i = head[v]; i != -1; i = e[i].next) { if (fn == 1) { if (dis[e[i].v] < dis[v] + e[i].ct) { dis[e[i].v] = dis[v] + e[i].ct; if (!vis[e[i].v]) { q.push(e[i].v); vis[e[i].v] = true; } } } else { if (dis[e[i].v] > dis[v] + e[i].ct) { dis[e[i].v] = dis[v] + e[i].ct; if (!vis[e[i].v]) { q.push(e[i].v); vis[e[i].v] = true; } } } } }}void spfa_path(int sta, int dis[], Edge e[], int head[], int fn) { if (fn == 1) { memset(dis, 0, sizeof (int) * 1005); } else { memset(dis, 0x3f, sizeof (int) * 1005); } memset(path, 0xff, sizeof (path)); memset(vis, 0, sizeof (vis)); queue<int>q; dis[sta] = 0; vis[sta] = true; q.push(sta); while (!q.empty()) { int v = q.front(); q.pop(); vis[v] = false; for (int i = head[v]; i != -1; i = e[i].next) { if (fn == 1) { if (dis[e[i].v] < dis[v] + e[i].ct) { dis[e[i].v] = dis[v] + e[i].ct; path[e[i].v] = v; if (!vis[e[i].v]) { q.push(e[i].v); vis[e[i].v] = true; } } } else { if (dis[e[i].v] > dis[v] + e[i].ct) { dis[e[i].v] = dis[v] + e[i].ct; path[e[i].v] = v; if (!vis[e[i].v]) { q.push(e[i].v); vis[e[i].v] = true; } } } } } }void prt(int x, int &first) { if (path[x] != -1) { prt(path[x], first); } if (first) { printf("%d", x); first = 0; } else { printf(" %d", x); }}int main() { int T; cin >> T; while (T--) { idx = ridx = -1; memset(head, 0xff, sizeof (head)); memset(rhead, 0xff, sizeof (rhead)); int a, b, c; cin >> N >> M >> K; for (int i = 0; i < M; ++i) { scanf("%d %d %d", &a, &b, &c); insert(a, b, c, e, head, idx); } for (int i = 0; i < K; ++i) { scanf("%d %d %d", &a, &b, &c); insert(a, b, c, re, rhead, ridx); } for (int i = 1; i <= N; ++i) { spfa(i, dis[i], e, head, 1); spfa(i, rdis[i], re, rhead, 2); } double Max = 0; int x, y; for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { if (rdis[j][i] != 0) { if (1.0*dis[i][j]/rdis[j][i] > Max) { x = i, y = j; Max = max(1.0*dis[i][j]/rdis[j][i], Max); } } } } int first = 1; spfa_path(y, rdis[x], re, rhead, 2); prt(path[x], first); spfa_path(x, dis[x], e, head, 1); prt(y, first); printf("n%.3fn", Max); } return 0; }
