#define OUR_FILE

#include<scil/scil.h>
#include<scil/constraints/atour.h>
#include<scil/constraints/path.h>
//#include<scil/constraints/disjunctive.h>
#include<LEDA/tuple.h>
#include<LEDA/stream.h>
#include<LEDA/string.h>
#include<fstream.h>

using namespace SCIL;
using namespace LEDA;

typedef two_tuple<node, node> prec;

LEDA::string read_next_line(istream& is) {
  LEDA::string s="#";
  while((!is.eof()) && ((s.head(1)=="#") || (s.length()==0) || (s.head(1)==" "))) {
    s.read_line(is);
  };
  if(is.eof()) s="";
  return s;
};


int main(int argc, char** argv) {

  // READ_GRAPH

  ifstream is(argv[1]);

  GRAPH<int,int> G;

  LEDA::string_istream s(read_next_line(is));
  int n,i,j,k;

  s>>n;
  node N[n+1];
  LEDA::string Names[n];

  cout<<n<<" nodes in the graph\n";

#ifdef OUR_FILE
  for(int i=0; i<n; i++) Names[i]=read_next_line(is);
#endif

  for(int i=0; i<n; i++) {
    N[i]=G.new_node(i);
  };

#ifdef OUR_FILE
  bool start=false;
  while(!is.eof()) {
    string_istream s(read_next_line(is));
    s>>i;
    if(!s.eof()) {
      if(i==-1) {
        i=n;
        if(start==false) {
          start=true;
          N[n]=G.new_node(n);
        }
      }
      s>>j; s>>k;
      //double d; s>>d; k=(int) d;
      cout<<i<<" "<<j<<" "<<k<<" edge\n";
      G.new_edge(N[i],N[j],k);
    }
  };
  if(start) {
    for(int i=0; i<n; i++) {
      G.new_edge(N[i],N[n],0);
    }
  };
#endif

#ifndef OUR_FILE
  for(i=0; i<n; i++) for(j=0; j<n; j++) {
    is>>k;
    if((k<10000000) && (i!=j))
      G.new_edge(N[i],N[j],k);
  }
#endif

  // END_READ_GRAPH

  ILP_Problem IP(Optsense_Min);

  edge e;
  row_map<edge> VM;
  forall_edges(e, G) {
    VM[e]=IP.add_variable(G[e],0,1, Vartype_Integer);
  };

  IP.add_sym_constraint(new ATOUR(G, VM));

  IP.optimize();

  int d=0;
  forall_edges(e, G) if(IP.get_solution(VM[e])>=0.5) {
    cout<<G[source(e)]<<" "<<G[target(e)]<<" "<<G[e]<<" edge\n";
    d+=G[e];
  } else G.del_edge(e);

  cerr<<argv[1]<<" "<<d<<endl;

  node u=N[0];
#ifdef OUR_FILE
  if(start==true) u=N[n];
#endif
  node v=u;
  do {
    if(G[u]!=n) cout<<G[u]<<" "<<Names[G[u]]<<endl;
    u=G.opposite(u,G.first_adj_edge(u));
  } while(u!=v);
  cout<<"\n\n";

  exit(0);
};