/*
 * e_038_cuplaj_maxim_cost_minim.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_max_flow_min_modified_for_dijsktra_nms
{
    struct Edge
    {
        int u, v; // edge u to v
        int c; // the capacity
        int z; // the cost of the edge
        int dir; // direction: forward (1) or backward (-1) edge
        Edge* re; // pointer to the reverse edge in the graph
        
        int id; // the id of the edge
    };

    void find_best_cost_bellman_ford(int S, vector<vector<Edge*>>& adj_list, vector<int>& best_cost)
    {
        int N = adj_list.size() - 1;
        list<int> Q;
        vector<char> in_queue;
        vector<int> bfs_levels; // the level of the nodes in a bfs search from S
        in_queue.resize(N + 1);
        bfs_levels.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;
        bfs_levels[S] = 1;
        int max_bfs_level = 1;

        //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 e : adj_list[u])
            {
                if (e->c <= 0) continue; //only positive capacities are processed here

                int v = e->v;
                int candidate_cost = best_cost[u] + e->z;
                if (candidate_cost < best_cost[v])
                {
                    best_cost[v] = candidate_cost;
                    bfs_levels[v] = bfs_levels[u] + 1;
                    max_bfs_level = max(bfs_levels[v], max_bfs_level);

                    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<Edge*>>& adj_list,
            int& flow_cost)
    {
        int max_flow = 0;
        flow_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> pii;
        priority_queue<pii, vector<pii>, std::greater<pii>> Q;
        vector<int> best_cost_augmented;
        vector<char> in_queue;
        vector<Edge*> parent_edges;

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

        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);
            std::fill(best_cost_new.begin(), best_cost_new.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& ep : parent_edges)
                ep = 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 c = 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 (c > best_cost_augmented[u]) continue;

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

                for (auto e : adj_list[u])
                {
                    int v = e->v;
                    //edge with positive capacity
                    if (in_queue[v] == 1 && e->c > 0)
                    {
                        //check-update the cost of the node
                        int augmented_cost_uv = best_cost_augmented[u] + e->z + 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));

                            parent_edges[v] = e;

                            //update the real best cost
                            best_cost_new[v] = best_cost_new[u] + e->z;
                        }
                    }
                }
            }

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

            //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 (parent_edges[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 = parent_edges[D]->c + 1;
                int node = D;
                while (node != S)
                {
                    Edge* e = parent_edges[node];
                    min_capacity = min(min_capacity, e->c);
                    node = e->u;
                }
                //increment the flow value
                max_flow += min_capacity;

                //update the capacity of edges in the residual graph
                node = D;
                while (node != S)
                {
                    Edge* e = parent_edges[node];
                    e->c -= min_capacity;
                    //also update the reverse edge
                    e->re->c += min_capacity;
                    node = e->u;
                    
                    //update the cost of the flow
                    flow_cost += min_capacity * e->z; 
                }
            }
            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_modified_for_dijsktra()
int main()
{
    using namespace e_032_cuplaj_maxim_min_cost_max_flow_min_modified_for_dijsktra_nms;

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

    int NL, NR, E, S, D;
    vector<vector<Edge*>> 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 total number of nodes: source + nodes left + nodes right + sink
    //id nodes left : 1 + id in file
    //id nodes right : 1 + NL + id_in_file
    int N = 1 + NL + NR + 1;
    adj_list.resize(N + 1);

    //set the source and the destination nodes
    S = 1;
    D = N;
    
    for (int k = 1; k <= E; k++)
    {
        //create the forward and it's backward edge
        Edge* e = new Edge;
        Edge* re = new Edge;

        ifs >> e->u >> e->v >> e->z;
        e->u += 1;
        e->v += 1 + NL;
        e->c = 1;
        e->dir = 1;
        e->re = re;
        e->id = k;

        re->u = e->v;
        re->v = e->u;
        re->c = 0;
        re->z = -e->z;
        re->dir = -1;
        re->re = e;
        re->id = -e->id;

        adj_list[e->u].push_back(e);
        adj_list[e->v].push_back(re);
    }

    ifs.close();

    //add nodes from the source 1 to each node of the set V
    for (int i = 1; i <= NL; i++)
    {
        //create the forward and it's backward edge
        Edge* e = new Edge;
        Edge* re = new Edge;
        e->u = 1;
        e->v = 1 + i;
        e->c = 1;
        e->z = 0;
        e->dir = 1;
        e->re = re;

        re->u = e->v;
        re->v = e->u;
        re->c = 0;
        re->z = -e->z;
        re->dir = -1;
        re->re = e;
        
        adj_list[e->u].push_back(e);
        adj_list[e->v].push_back(re);
    }

    //add nodes from the nodes in the set R to the sink 1 + NL + NR + 1
    for (int i = 1; i <= NR; i++)
    {
        //create the forward and it's backward edge
        Edge* e = new Edge;
        Edge* re = new Edge;
        e->u = 1 + NL + i;
        e->v = 1 + NL + NR + 1;
        e->c = 1;
        e->z = 0;
        e->dir = 1;
        e->re = re;

        re->u = e->v;
        re->v = e->u;
        re->c = 0;
        re->z = -e->z;
        re->dir = -1;
        re->re = e;

        adj_list[e->u].push_back(e);
        adj_list[e->v].push_back(re);
    }

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


    ofstream ofs(out_file.c_str());
    ofs << max_flow << ", " << flow_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 (auto& e : adj_list[u])
               if (e->dir == 1 && e->re->c > 0) //the edge e has flow
                   ofs << e->id << " ";
    ofs.close();

    //release the memory
    for (int u = 1; u <= N; u++)
        for (vector<Edge*>::iterator it = adj_list[u].begin(); it != adj_list[u].end(); it++)
            delete *it;

    return 0;
}