/*
 * e_038_cuplaj_maxim_cost_minim_matrices.cpp
 *
 *  Created on: May 29, 2015
 *      Author: Marius
 */

#include <iostream>
#include <utility>
using namespace std;
#include <fstream>
#include <queue>
#include <list>
#include <vector>
#include <string>
#include <algorithm>
#include <limits>
#include <set>

namespace e_032_cuplaj_maxim_min_cost_dijsktra_matrices_nms
{
    const int MAX_N = 2 * 300 + 2;
    int cap[MAX_N + 1][MAX_N + 1];
    int cst[MAX_N + 1][MAX_N + 1];
    int edge_ids[MAX_N + 1][MAX_N + 1];
    
    void find_best_cost_bellman_ford(int S, vector<vector<int>>& adj_list, vector<int>& best_cost)
    {
        int N = adj_list.size() - 1;
        list<int> Q;
        vector<char> in_queue;
        in_queue.resize(N + 1);

        std::fill(best_cost.begin(), best_cost.end(), std::numeric_limits<int>::max());
        std::fill(in_queue.begin(), in_queue.end(), 0);

        Q.push_back(S);
        in_queue[S] = 1;
        best_cost[S] = 0;

        //while ( !Q.empty() && max_bfs_level <= N )
        // the problem statement guarantees there are no negative cycles
        while (!Q.empty())
        {
            // pop one element from the list
            int u = Q.front();
            Q.pop_front();
            in_queue[u] = 0;

            //parse the adjacency list and look for possible better costs
            for (auto v : adj_list[u])
            {
                if (cap[u][v] <= 0) continue; //only positive capacities are processed here

                int candidate_cost = best_cost[u] + cst[u][v];
                if (candidate_cost < best_cost[v])
                {
                    best_cost[v] = candidate_cost;
                    if (!in_queue[v])
                    {
                        Q.push_back(v);
                        in_queue[v] = 1;
                    }
                }
            }

        }
    }

    int find_max_flow_ford_fulkerson(int N, int S, int D, vector<vector<int>>& adj_list,
            int& total_cost)
    {
        int max_flow = 0;
        total_cost = 0;

        //find the initial best cost using the bellman ford algorithm
        //the algorithm only uses the cost and ignores the capacities of the edges
        vector<int> best_cost_prev, best_cost_new;
        best_cost_prev.resize(N + 1);
        best_cost_new.resize(N + 1);

        find_best_cost_bellman_ford(S, adj_list, best_cost_prev);

        typedef pair<int, int> p_ii;
        priority_queue<p_ii, vector<p_ii>, std::greater<p_ii>> Q;
        vector<int> best_cost_augmented;
        vector<char> in_queue;
        vector<int> parents;

        best_cost_augmented.resize(N + 1);
        in_queue.resize(N + 1);
        parents.resize(N + 1);

        std::fill(best_cost_new.begin(), best_cost_new.end(), std::numeric_limits<int>::max() / 2);

        bool has_s2t_path = true;
        while (has_s2t_path)
        {
            //Dijkstra
            std::fill(best_cost_augmented.begin(), best_cost_augmented.end(),
                    std::numeric_limits<int>::max() / 2);

            best_cost_augmented[S] = 0;
            best_cost_new[S] = 0;

            for (int u = 1; u <= N; u++)
                Q.push(make_pair(best_cost_augmented[u], u));

            std::fill(in_queue.begin(), in_queue.end(), 1);

            for (auto& p : parents)
                p = 0;

            //find a path from source to sink in the residual graph
            //only edges with positive capacities should be included in the path
            while (!Q.empty())
            {
                //pop the first element in the set
                auto top = Q.top();
                int u = top.second;
                int bu = top.first;
                Q.pop();

                //if not the true minimum, do nothing
                //take care about multiple costs for the same node in the priority queue
                if (bu > best_cost_augmented[u]) continue;

                in_queue[u] = 0; // no longer in queue

                for (int v : adj_list[u])
                {
                    //edge with positive capacity
                    int cap_uv = cap[u][v], cst_uv = cst[u][v];
                    if (in_queue[v] == 1 && cap_uv > 0)
                    {
                        //check-update the cost of the node
                        int augmented_cost_uv = best_cost_augmented[u] + cst_uv + best_cost_prev[u]
                                - best_cost_prev[v];

                        if (augmented_cost_uv < best_cost_augmented[v])
                        {
                            //update the cost of the node                           
                            best_cost_augmented[v] = augmented_cost_uv;

                            //insert the updated cost
                            //take care, the previous best cost, is still in the priority queue
                            Q.push(make_pair(best_cost_augmented[v], v));

                            parents[v] = u;

                            //update the real best cost
                            best_cost_new[v] = best_cost_new[u] + cst_uv;
                        }
                    }
                }
            }

            //prepare the updated cost for the next iteration
            //for (int i = 1; i <= N; i++)
            //best_cost_prev[i] = best_cost_new[i];
            best_cost_prev = best_cost_new;

            //if the sink was reached, there is a path from source to sink
            //the path is the shortest, due to the bellman-ford algorithm
            if (parents[D] != 0)
            {
                // we have a path from source to sink
                // update the residual graph
                //
                // parse the path we have found from sink to source, via parent edges
                // and find the minimum capacity
                int min_capacity = cap[parents[D]][D] + 1;
                int node = D;
                while (node != S)
                {
                    int p = parents[node];
                    min_capacity = min(min_capacity, cap[p][node]);
                    node = p;
                }
                //increment the flow value
                max_flow += min_capacity;

                //update the capacity of edges in the residual graph
                node = D;
                while (node != S)
                {
                    int p = parents[node];
                    cap[p][node] -= min_capacity;
                    //also update the reverse edge
                    cap[node][p] += min_capacity;

                    //update the total cost
                    total_cost += min_capacity * cst[p][node];

                    node = p; //go to the parent node
                }
            }
            else
                has_s2t_path = false; //no more paths from s to t
        }

        return max_flow;
    }
}

//int e_032_cuplaj_maxim_min_cost_max_flow_min_dijsktra_matrices()
int main()
{
    using namespace e_032_cuplaj_maxim_min_cost_dijsktra_matrices_nms;

    string in_file = "cmcm.in";
    string out_file = "cmcm.out";

    int NL, NR, E, S, D;
    vector<vector<int>> adj_list;

    ifstream ifs(in_file.c_str());
    if (!ifs.is_open())
    {
        cout << "Input file not found" << endl;
        return -1; // no input file
    }
    ifs >> NL >> NR >> E;

    //the number of nodes
    int N = 1 + NL + NR + 1;
    S = 1;
    D = N;

    adj_list.resize(N + 1);
    
    for (int k = 1; k <= E; k++)
    {
        //create the forward and it's backward edge
        int u, v, z;
        ifs >> u >> v >> z;
        //adjust the ids of the nodes
        u += 1;
        v += 1 + NL;
        
        cap[u][v] = 1;
        cst[u][v] = z;
        edge_ids[u][v] = k;
        
        cap[v][u] = 0;
        cst[v][u] = -z;        
        edge_ids[v][u] = -k;
        
        adj_list[u].push_back(v);
        adj_list[v].push_back(u);
    }

    ifs.close();

    //create edges from source to nodes in L
    for (int i = 1; i <= NL; i++)
    {
        int i1 = i + 1;
        cap[1][i1] = 1;
        cst[1][i1] = 0;
        edge_ids[1][i1] = 0;
        
        //also residual edge
        cap[i1][1] = 0;
        cst[i1][1] = 0;
        edge_ids[i1][1] = 0;
        
        adj_list[1].push_back(i1);
        adj_list[i1].push_back(1);

    }
    //create edges from nodes of R to the sink
    for (int i = 1; i <= NR; i++)
    {
        int i1 = 1 + NL + i;
        cap[i1][N] = 1;
        cst[i1][N] = 0;
        edge_ids[i1][N] = 0;
        
        //also residual edge
        cap[N][i1] = 0;
        cst[N][i1] = 0;
        edge_ids[N][i1] = 0;
        
        adj_list[i1].push_back(N);
        adj_list[N].push_back(i1);

    }

    int total_cost;
    int max_flow = find_max_flow_ford_fulkerson(N, S, D, adj_list, total_cost);

    ofstream ofs(out_file.c_str());
    ofs << max_flow << " " << total_cost << endl;
    //parse the adjacency list and find the pairs = edges from V to R having flow
    for (int u = 2; u <= 1 + NL; u++)
    {
        for (int v : adj_list[u])
        {
            if (edge_ids[u][v] > 0 && cap[v][u] > 0) //the edge has flow
                ofs << edge_ids[u][v] << " ";
        }
    }
    ofs.close();

    return 0;
}