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.kernel.solver.Solver;
import choco.kernel.model.variables.integer.IntegerVariable;
import java.io.*;
import java.util.*;

public class KE2 { 

    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 flatW[];             // w[][] flattened
    Model modl;
    Solver sol;
    int n,sumW;

    public KE2(int n,String fname) throws Exception {
	MyIo fin = new MyIo(fname);
	value  = makeIntVar("value",0,9999999);
	A      = new IntegerVariable[n][n];
	flatA  = new IntegerVariable[n*n];
	next   = new IntegerVariable[n];
	w      = new int[n][n];
	flatW  = new int[n*n];
	modl   = new CPModel();
	sol    = new CPSolver();
	edge   = new int[n][n];
	this.n = n;
	for (int i=0;i<n;i++)
	    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;
	}
	fin.close();
	for (int i=0;i<n;i++){
	    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));
	}
	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++)
	    for (int j=0;j<n;j++){
		flatA[k] = A[i][j];
		flatW[k] = w[i][j];
		sumW = sumW + w[i][j];
		k++;
	    }	
    }

    public void validTriple(int i,int j,int k){
	modl.addConstraint(implies(and(eq(next[i],j),eq(next[j],k)),eq(next[k],i)));
    }

    public void validTriple(){
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++)
		if (edge[i][j] == 1)
		    for (int k=0;k<n;k++)
			if (i!=j && i!=k && j!=k && edge[j][k] == 1)
			    validTriple(i,j,k);
    }

    public void edge(int i,int j){
	modl.addConstraint(ifOnlyIf(eq(next[i],j),eq(A[i][j],1)));
    }

    public void edge(){
	for (int i=0;i<n;i++)
	    for (int j=0;j<n;j++)
		edge(i,j);
    }

    public void cost(){
	modl.addVariable(value);
	//modl.addConstraint(eq(value,scalar(flatA,flatW)));
	modl.addConstraint(eq(value,plus(mult(sumW,sum(flatA)),scalar(flatA,flatW))));
    }
	    
    public Model getModel(){return modl;}
    public IntegerVariable[][] getA(){return A;}

    public void init(){
	validTriple();
	edge();
	cost();
	modl.addConstraint(allDifferent(next));
	sol.read(modl);
	sol.setVarIntSelector(new MinDomain(sol,sol.getVar(next)));
    }

    public Boolean solve(){return sol.solve(false);}
    public Boolean maximize(){return sol.maximize(sol.getVar(value),true);}
    public void solveAll(){
	int noSol = 0;
	if (sol.solve().booleanValue()){
	    noSol++;
	    //System.out.println(this);
	    while (sol.nextSolution().booleanValue()){
		noSol++;
		//System.out.println(this);
	    }
	}
	System.out.println("Number of solutions: " + noSol);
    }

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

    public String toString(){
	String s = "";
	/*
	for (int i=0;i<n;i++){
	    if (i < 9) s = s + (i+1) + "   ";
	    else s = s + (i+1) + "  ";
	    for (int j=0;j<n;j++)
		s = s + w[i][j] + " ";
	    s = s + "\n";	    
	}
	s = s + "\n";
	for (int i=0;i<n;i++){
	    if (i < 9) s = s + (i+1) + "   ";
	    else s = s + (i+1) + "  ";
	    for (int j=0;j<n;j++)
		s = s + sol.getVar(A[i][j]).getVal() + " ";
	    s = s + "\n";	    
	}
	s = s + "\n";
	for (int i=0;i<n*n;i++) s = s + flatW[i] + " ";
	s = s + "\n";
	for (int i=0;i<n*n;i++) s = s + sol.getVar(flatA[i]).getVal() + " ";
	s = s + "\n";
	*/
	for (int i=0;i<n;i++){
	    int j = sol.getVar(next[i]).getVal();
	    if (edge[i][j] != 0){
		s = s + (i+1) +" -> "+ (j+1) +" = "+ w[i][j] + "\n";
		//System.out.println(i+1 +" -> "+ (sol.getVar(next[i]).getVal()+1));
	    }
	}
	s = s + "\n" + sol.getVar(value).pretty();
	return s;
    }
  
    public static void main(String[] args) throws Exception {
	int n = Integer.parseInt(args[0]); // number of vertices  
	KE2 ke = new KE2(n,args[1]);
	ke.init();
	ke.maximize();
	//ke.solveAll();
	System.out.println(ke);
	ke.stats();
    }
}