import static choco.Choco.*;
import choco.cp.model.CPModel;
import choco.cp.solver.CPSolver;
import choco.kernel.model.Model;
import choco.cp.solver.search.integer.varselector.*;
import choco.cp.solver.search.integer.valselector.*;
import choco.kernel.solver.Solver;
import choco.kernel.model.variables.integer.IntegerVariable;
import java.io.*;
import java.util.*;

public class KE5 { 

    IntegerVariable value;    // the value of the solution, maximise
    IntegerVariable A[][];    // adjacency matrix
    IntegerVariable next[];   // single successor
    IntegerVariable flatA[];  // A[][] flattened
    int w[][];                // weight
    int edge[][];             // inputted adjacency matrix (edges may have 0 weight)
    int deg[];                // degree of i
    int flatW[];              // w[][] flattened
    int flatE[];              // edge[][] flattened
    Model modl;
    Solver sol;
    int n,sumW,maxDonors;

    public KE5(int n,String fname) throws Exception {
	MyIo fin = new MyIo(fname);
	A      = new IntegerVariable[n][n];
	flatA  = new IntegerVariable[n*n];
	next   = new IntegerVariable[n];
	w      = new int[n][n];
	edge   = new int[n][n];
	deg    = new int[n];
	flatW  = new int[n*n];
	flatE  = new int[n*n];
	modl   = new CPModel();
	sol    = new CPSolver();
	this.n = n;
	maxDonors = 0;
	for (int i=0;i<n;i++){
	    deg[i] = 0;
	    for (int j=0;j<n;j++) {w[i][j] = 0;edge[i][j] = 0;}
	}
	while (fin.hasMoreData()){
	    int x = fin.getNextInt();
	    int y = fin.getNextInt();
	    int z = fin.getNextInt();
	    w[x-1][y-1] = Math.max(z,w[x-1][y-1]);
	    edge[x-1][y-1] = 1;
	    deg[x-1]++;
	}
	fin.close();
	removeRedundantEdges();
	for (int i=0;i<n;i++){
	    if (deg[i] > 0){
		next[i] = makeIntVar("next[" + i + "]",0,n-1,"cp:enum");
		for (int j=0;j<n;j++)
		    if (i != j && edge[i][j] == 0) modl.addConstraint(neq(next[i],j));
	    }
	    else 
		next[i] = makeIntVar("next[" + i + "]",i,i);
	}
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++)
		A[i][j] = makeIntVar("A[" + i +"]["+ j +"]",0,1);
	int k = 0; sumW = 0;
	for (int i=0;i<n;i++){
	    int maxW = 0;
	    if (deg[i] > 0) maxDonors++;
	    for (int j=0;j<n;j++){
		flatA[k] = A[i][j];
		flatW[k] = w[i][j];
		flatE[k] = edge[i][j];
		maxW     = Math.max(maxW,+ w[i][j]);
		k++;
	    }
	    sumW = sumW + maxW;
	}
    }

    public void makeNext(int i){
	int[]d = new int[deg[i] + 1];
	int k = 0;
	for (int j=0;j<n;j++)
	    if (edge[i][j] == 1){
		d[k] = j;
		k++;
	    }
	d[deg[i]] = i;
	next[i] = makeIntVar("next[" + i + "]",d);
    }
	
    public int removeRedundantEdges(){
	int removals = 0;
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++){
		if (i != j && edge[i][j] == 1){
		    Boolean found = edge[j][i] == 1;
		    for (int k=0;k<n && !found;k++)
			found = (edge[i][j] + edge[j][k] + edge[k][i]) == 3;
		    if (!found) {edge[i][j] = 0; deg[i]--; removals++;}
		}
	    }
	//System.out.println(removals);
	return removals;
    }			
	
    public void edge(){
	for (int i=0;i<n;i++)	   
	    for (int j=0;j<n;j++)
		if (edge[i][j] == 1)
		    modl.addConstraint(ifOnlyIf(eq(next[i],j),eq(A[i][j],1)));
		else
		    modl.addConstraint(eq(A[i][j],0));
    }

    public void cost(String s){
	if (s.equals("donors")){ // max donors
	    value  = makeIntVar("value",0,maxDonors);
	    modl.addVariable(value);
	    modl.addConstraint(eq(value,scalar(flatA,flatE)));
	}
	else
	    if (s.equals("weight")){ // max weight
		value  = makeIntVar("value",0,sumW);
		modl.addVariable(value);
		modl.addConstraint(eq(value,scalar(flatA,flatW))); 
	    }
	    else 
		if (s.equals("both")){ // max donors + weight
		    value  = makeIntVar("value",0,(maxDonors+1)*sumW);
		    modl.addVariable(value);
		    modl.addConstraint(eq(value,plus(mult(sumW,sum(flatA)),scalar(flatA,flatW)))); 
		}
    }
	    
    public Model getModel(){return modl;}

    public void setNodeLimit(int nds){if (nds > 0) sol.setNodeLimit(nds);}

    public void stats(){
	sol.printRuntimeSatistics();
	System.out.println("nbSol: " + sol.getNbSolutions());
    }

    public void showData(){
	for (int i=0;i<n;i++){
	    if (i<9) System.out.print(" "); System.out.print((i+1) +" ");	    
	    for (int j=0;j<n;j++)
		System.out.print(" "+ edge[i][j]);
	    System.out.println();
	}
    }

    public String toString(){
	int donations = 0, score = 0;
	String s = "";
	for (int i=0;i<n;i++){
	    int j = sol.getVar(next[i]).getVal();
	    if (edge[i][j] != 0){
		donations++;
		score = score + w[i][j];
		s = s + (i+1) +" -> "+ (j+1) +" = "+ w[i][j] + "\n";
	    }
	}
	s = s +"\ndonations: "+ donations +"  score: "+ score;
	s = s +"\n"+ sol.getVar(value).pretty();
	return s;
    }

    public Boolean solve(){return sol.solve(false);}
    public Boolean maximize(){return sol.maximize(sol.getVar(value),false);}

    public void init(String costFunction){
	edge();
	cost(costFunction);
	modl.addConstraint(allDifferent(next));
	sol.read(modl);
	sol.post(new LegalCycles(sol,sol.getVar(next))); 
	//sol.setVarIntSelector(new StaticVarOrder(sol.getVar(next)));
	sol.setVarIntSelector(new MinDomain(sol,sol.getVar(next)));
	//sol.setVarIntSelector(new DomOverWDeg(sol,sol.getVar(next)));
	//sol.setVarIntSelector(new RandomIntVarSelector(sol,sol.getVar(next),(long)9821735));
	//sol.setValIntSelector(new RandomIntValSelector());
    }
  
    public static void main(String[] args) throws Exception {
	int n               = Integer.parseInt(args[0]); // number of vertices  
	KE5 ke              = new KE5(n,args[1]);
	int nodeLimit       = Integer.parseInt(args[2]);
	String costFunction = args[3];
	ke.init(costFunction);
	ke.setNodeLimit(nodeLimit);
	ke.maximize();
	//System.out.println(ke.solve());
	System.out.println(ke);
	ke.stats();
    }
}