Mafia

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        int[][] graph = DefaultGraph(n);

        string input;
        int setCount = 1;
        MaxFlow m;
        while (!(input = Console.ReadLine()).Equals("end"))
        {
            int[] data = input.Split(new[] { ' ', '-' }, StringSplitOptions.RemoveEmptyEntries)
                .Select(int.Parse)
                .ToArray();
            if (data.Length == 1)
            {
                m = new MaxFlow(n);

                Console.WriteLine($"Group {setCount++}: {m.fordFulkerson(graph, 0, n - 1)}");
                n = data[0];
                graph = DefaultGraph(n);
                continue;
            }
            int a = data[0] - 1, b = data[1] - 1, p = data[2];
            graph[a][b] = p;
            graph[b][a] = p;
        }

        m = new MaxFlow(n);
        Console.WriteLine($"Group {setCount++}: {m.fordFulkerson(graph, 0, n - 1)}");
    }

    private static int[][] DefaultGraph(int n)
    {
        var graph = new int[n][];
        for (int i = 0; i < n; i++)
        {
            graph[i] = new int[n];
            for (int j = 0; j < n; j++)
            {
                graph[i][j] = 0;
            }
        }
        return graph;
    }
}

class MaxFlow
{
    private int V;//Number of vertices in graph
    public MaxFlow(int v)
    {
        this.V = v;
    }

    /* Returns true if there is a path from source 's' to sink
      't' in residual graph. Also fills parent[] to store the
      path */
    bool bfs(int[][] rGraph, int s, int t, int[] parent)
    {
        // Create a visited array and mark all vertices as not
        // visited
        bool[] visited = new bool[V];
        for (int i = 0; i < V; ++i)
            visited[i] = false;

        // Create a queue, enqueue source vertex and mark
        // source vertex as visited
        Queue<int> queue = new Queue<int>(new[] { s });

        visited[s] = true;
        parent[s] = -1;

        // Standard BFS Loop
        while (queue.Count != 0)
        {
            int u = queue.Dequeue();

            for (int v = 0; v < V; v++)
            {
                if (visited[v] == false && rGraph[u][v] > 0)
                {
                    queue.Enqueue(v);
                    parent[v] = u;
                    visited[v] = true;
                }
            }
        }

        // If we reached sink in BFS starting from source, then
        // return true, else false
        return (visited[t] == true);
    }

    // Returns tne maximum flow from s to t in the given graph
    public int fordFulkerson(int[][] graph, int s, int t)
    {
        int u, v;

        // Create a residual graph and fill the residual graph
        // with given capacities in the original graph as
        // residual capacities in residual graph

        // Residual graph where rGraph[i][j] indicates
        // residual capacity of edge from i to j (if there
        // is an edge. If rGraph[i][j] is 0, then there is
        // not)
        int[][] rGraph = new int[V][];
        for (int i = 0; i < V; i++)
        {
            rGraph[i] = new int[V];
        }

        for (u = 0; u < V; u++)
            for (v = 0; v < V; v++)
                rGraph[u][v] = graph[u][v];

        // This array is filled by BFS and to store path
        int[] parent = new int[V];

        int max_flow = 0;  // There is no flow initially

        // Augment the flow while tere is path from source
        // to sink
        while (bfs(rGraph, s, t, parent))
        {
            // Find minimum residual capacity of the edhes
            // along the path filled by BFS. Or we can say
            // find the maximum flow through the path found.
            int path_flow = int.MaxValue;
            for (v = t; v != s; v = parent[v])
            {
                u = parent[v];
                path_flow = Math.Min(path_flow, rGraph[u][v]);
            }

            // update residual capacities of the edges and
            // reverse edges along the path
            for (v = t; v != s; v = parent[v])
            {
                u = parent[v];
                rGraph[u][v] -= path_flow;
                rGraph[v][u] += path_flow;
            }

            // Add path flow to overall flow
            max_flow += path_flow;
        }

        // Return the overall flow
        return max_flow;
    }
}