#include <cmath>#include <cstdio>#include <memory.h>#include <algorithm>#include <iomanip>#include <iostream>#include <vector>using namespace std;#define EDGE (200000 + 5)#define MAX (1000+50)#define min(a,b) ((a) < (b) ? (a) : (b))int cases = 1;class Dinic{public: int n, graph[MAX][MAX], c[MAX][MAX], f[MAX][MAX]; int delta[MAX], from[MAX]; int s, t; int mark[MAX]; int queue[MAX]; int graph1[MAX][MAX], step[MAX]; int visited[MAX]; struct link { int v; int id; int nxt; }link[EDGE * 2]; int edgeN; void addlink(int u, int v, int id); int mat[MAX][MAX]; int ans[EDGE]; int ret; int eN; void dfs(int s); void init(); void in(); void out(); void addEdge(int x, int y, int v); void dinic(); int create_graph(); void increase_flow();};void Dinic::init(){ memset(c, 0, sizeof(c)); memset(graph, 0, sizeof(graph)); memset(visited, 0, sizeof(visited)); memset(mat, 0, sizeof(mat));}void Dinic::addEdge(int x, int y, int v){ if (!c[x][y] && !c[y][x]) { graph[x][++graph[x][0]] = y; graph[y][++graph[y][0]] = x; } c[x][y] += v;}void Dinic::addlink(int u, int v, int id){ link[edgeN].nxt = link[u].nxt; link[edgeN].v = v; link[edgeN].id = id; link[u].nxt = edgeN++;}void Dinic::in(){ int m, i, x, y, cc, k, j; scanf("%d", &n); scanf("%d", &m); scanf("%d", &k); s = 1, t = n + 1; for (i = 1; i <= t; i++) link[i].nxt = -1; edgeN = t + 1; for (i = 1, j = 1; i <= m; i++) { scanf("%d%d%d", &x, &y, &cc); addlink(x, y, j++); mat[x][y] = 1; addEdge(x, y, cc); } ret = 0; for (i = 1; i <= k; i++) { scanf("%d%d", &x, &cc); mat[x][t] = 1; addEdge(x, t, cc); ret += cc; } n = t;}void Dinic::dfs(int x){ int i, u; visited[x] = 1; for (i = 1; i <= graph[x][0]; i++) { u = graph[x][i]; if (!visited[u] && (f[x][u] - f[u][x] < c[x][u])) dfs(u); }}void Dinic::out(){ int i, j, sum = 0, k; for (i = 1; i <= n; i++) sum += f[i][t] - f[t][i]; printf("Case %d: %dn", cases++, ret - sum); dfs(s); eN = 0; for (i = 1; i < n; i++) { k = link[i].nxt; while (k != -1) { j = link[k].v; if (visited[i] && !visited[j]) ans[eN++] = link[k].id; k = link[k].nxt; } } printf("%d", eN); sort(ans, ans + eN); for (i = 0; i < eN; i++) { printf(" %d", ans[i]); } printf("n");}int Dinic::create_graph(){ int i, j, k, id; for (i = 1; i <= n; i++) graph1[i][0] = 0; queue[queue[0] = 1] = s; memset(step, 0xFF, sizeof(step)); step[s] = 0; for (i = 1; i <= queue[0]; i++) for (id = queue[i], j = 1; j <= graph[id][0]; j++) if (f[id][k = graph[id][j]] < c[id][k] || f[k][id]) { if (step[k] == -1) { step[k] = step[id] + 1; queue[++queue[0]] = k; } if (step[k] == step[id] + 1) graph1[id][++graph1[id][0]] = k; } return step[t] != -1; }void Dinic::increase_flow(){ int i, j; memset(mark, 0, sizeof(mark)); while (!mark[s]) { memset(delta, 0, sizeof(delta)); delta[s] = 1000000000; for (i = s; i != t; i = j) { while (graph1[i][0] > 0 && mark[graph1[i][1]]) graph1[i][1] = graph1[i][graph1[i][0]--]; if (graph1[i][0] == 0) { mark[i] = 1; break; } j = graph1[i][1]; if (f[i][j] < c[i][j]) { delta[j] = min(delta[i], c[i][j] - f[i][j]); from[j] = i; } else if (f[j][i]) { delta[j] = min(delta[i], f[j][i]); from[j] = -i; } } if (i == t) for (; i != s; i = j) if ((j = from[i]) > 0) { f[j][i] += delta[t]; if (f[j][i] == c[j][i]) graph1[j][1] = graph1[j][graph1[j][0]--]; } else { f[i][j = -j] -= delta[t]; if (f[i][j] == 0) graph1[j][1] = graph1[j][graph1[j][0]--]; } }}void Dinic::dinic(){ memset(f, 0, sizeof(f)); while (create_graph()) increase_flow();}Dinic dic;int main(){ int t; scanf("%d", &t); while (t--) { dic.init(); dic.in(); dic.dinic(); dic.out(); } return 0;}
