#include <iostream>
#include <vector>
#include <map>
#include <list>
#include <utility>
#include <time.h>
#include <unistd.h>

// ==== using ===== //
using std::cout;
using std::cerr;
using std::endl;
// ================ // 


// ===== class ====== //

class nodeClass
{
  public:
    nodeClass(){ preIdx = -1; nextIdx = -1; }
    int index;
    bool done;
    double cost;

    //nodeClass *pre;
    //nodeClass *next;

    int preIdx;
    int nextIdx;
    std::vector<nodeClass> optRouteInfo;

    int getIndex(){return index; }
    int getIndexForOut(){ return index + 1; }
    std::vector<int> routeTo(int i);

    std::map<int, std::vector<int>> routeToMap;

};


class edgeClass
{
  public:
    edgeClass(){ from = NULL; to = NULL; }
    double dist;
    nodeClass *from;
    nodeClass *to;

};

class orderClass
{
  public:
    bool done;
    int id;
    int ordertime;
    int waitingtime;
    nodeClass *customer;

    double dScore(double dt1, double dt2);
};


// ================= //

// ==== global ======= //
clock_t start, end;
int V, E, Tmax, nowTime;
std::map<int, std::map<int, edgeClass> > edgeMap;
std::vector<std::vector<edgeClass> > edges;
std::map<int, nodeClass> nodeMap;
std::vector<nodeClass> nodes;
std::vector<std::vector<orderClass> > orders;
std::vector<int> ansBestRoute;
std::vector<int> ansBestRoute2;
// ==================== //


// ===== function ====== //

int Import();
int Export();
int Opt();
int GatherOrder(std::vector<orderClass> &orders, std::vector<orderClass> &notDelivOrders, int t1, int t2);
int SearchRoute(std::vector<orderClass> &sOrders, std::vector<orderClass> &notDelivOrders, double &score, std::vector<int> &aRouteEdge);
int createFeasibleRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute);
int createRoute(std::vector<int> &pathNodes, std::vector<int> &aRoute);
int ImproveTestRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute);

int Dikstra(int fromIdx, int toIdx);

//double GetRouteDist(std::list<int> &aRoute);
//double GetScoreRoute(std::vector<orderClass> &sOrders, std::list<int> &aRoute);
double GetRouteDist(std::vector<int> &aRoute);
double GetScoreRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute);
double GetScoreRoute2(std::vector<int> &aRoute);

void displayRoute(std::vector<int> &aRoute);
void outputRoute(std::vector<int> &aRoute);

double GetDist(int i, int j)
{
  if(i == j)
  { return 0; }

  std::map<int, edgeClass> *tmpMap = &edgeMap[i];

  if(tmpMap->find(j) == tmpMap->end())
  { return 1e+16; }
  else 
  { return tmpMap->at(j).dist; }
}
// ==================== //

int main() 
{

  int error = 0;

  //srand((unsigned int) time(NULL));
  start = clock();

  error = Import();
  error = Opt();
  error = Export();

  cerr << "done[opt] " << endl;

  return 0;
}

int Import()
{
  int error = 0;
  std::vector<std::vector<std::pair<int, int> > > G(V);

  // recieve |V| and |E|
  std::cin >> V >> E;

  // create nodes
  for(int i = 0; i < V; ++i)
  { 
    nodeClass aNode;
    aNode.index = i;
    aNode.done = false;

    nodes.push_back(aNode);
    nodeMap[i] = aNode;
  }

  for(int i = 0; i < V; ++i)
  { edges.push_back(std::vector<edgeClass>()); }

  for(int i = 0; i < E; i++) 
  {
    // recieve edges
    int u, v, d; std::cin >> u >> v >> d;
    u--; v--;
    //G[u].push_back({v, d});
    //G[v].push_back({u, d});

    edgeClass aEdge1, aEdge2;
    aEdge1.from = &nodeMap[u];
    aEdge1.to = &nodeMap[v];
    aEdge1.dist = d;

    aEdge2.from = &nodeMap[v];
    aEdge2.to = &nodeMap[u];
    aEdge2.dist = d;

    edgeMap[u][v] = aEdge1;
    edgeMap[v][u] = aEdge2;

    edges[u].push_back(aEdge1);
    edges[v].push_back(aEdge2);
  }

  std::cin >> Tmax;

  // recieve order info
  int nOrder = 0;
  for(int i = 0; i < Tmax; i++) 
  {
    int Nnew; std::cin >> Nnew;
    std::vector<orderClass> tmpvec;

    for(int j = 0; j < Nnew; j++)
    {
      int new_id, dst; 
      std::cin >> new_id >> dst;
      --dst;

      orderClass aOrder;
      aOrder.id = new_id;
      aOrder.ordertime = i;
      aOrder.customer = &nodeMap[dst];

      tmpvec.push_back(aOrder);
      ++nOrder;
    }

    orders.push_back(tmpvec);
  }

  cerr << "done Data Import... {V, E, O} = {" << V << ", " << E << ", " << nOrder << "} " << endl;
  return error;
}

int Export()
{
  int error = 0;

  outputRoute(ansBestRoute);

  return error;

}

int Opt()
{

  int error = 0;
  try
  {
    int nOrder = 0;
    int lastTime = 0;
    bool fin = false;
    double score_tot = 0.0;
    double maxVal = 0.0;

    //最短経路チェック
    for(int i = 0; i < nodes.size(); ++i)
    { Dikstra(i, -1); }
    //

    std::vector<orderClass> stackedOrders, notDelivOrders;
    std::vector<int> routeNodes, routeEdges;
    std::map<double, std::vector<int>> routeNodesMap;

    const int N = 50;

    for(int i = 0; i < N; ++i)
    {
      nowTime = 0;
      score_tot = 0.0;
      routeNodes.clear(); routeEdges.clear();

      routeNodes.push_back(0);

      while(!fin)
      {
	//decide waiting time
	int waitingTime_startpoint = rand() % 100 ;
	nowTime += waitingTime_startpoint;

	//gather orders
	stackedOrders.clear();
	error = GatherOrder(stackedOrders, notDelivOrders, lastTime, nowTime);

	if(error == 1 && nowTime >= Tmax)
	{ break; }

	lastTime = nowTime + 1;

	if(stackedOrders.size() == 0)
	{ 
	  nowTime += 1; 
	  routeNodes.push_back(0); 
	  routeEdges.push_back(0);
	  continue; 
	}

	double score = 0;
	std::vector<int> aRouteEdge;
	aRouteEdge.reserve(10000);
	error = SearchRoute(stackedOrders, notDelivOrders, score, aRouteEdge);

	std::map<int, int> notDelivMap;
	for(int i = 0; i < notDelivOrders.size(); ++i)
	{ notDelivMap[notDelivOrders[i].id] = 1; }

	for(int i = 0; i < stackedOrders.size(); ++i)
	{
	  if(notDelivMap.find(stackedOrders[i].id) != notDelivMap.end())
	  { continue; }
	  routeNodes.push_back(stackedOrders[i].customer->index);
	}
	routeNodes.push_back(0);

	for(int i = 0; i < aRouteEdge.size() - 1; ++i)
	{ routeEdges.push_back(aRouteEdge[i]); }

	score_tot += score;

      }

      double score = GetScoreRoute2(routeEdges);
      routeNodesMap[score] = routeNodes;
      cerr << "TIME " << nowTime << endl;
      cerr << "score = " << score << endl;

    }

    ansBestRoute = routeEdges;
    ansBestRoute2 = routeEdges;

    std::vector<int> tmpRoute;
    std::vector<int> bestRouteNodes = routeNodes;

    for(int loop = 0; loop < 100000; ++loop)
    {
      int ii = rand() % routeNodesMap.size();
      int jj = rand() % routeNodesMap.size();

      if(ii == 0 || jj == 0)
      { continue; }

      std::vector<int> A, B;
      int n = 0;
      for(auto itr = routeNodesMap.begin(); itr != routeNodesMap.end(); ++itr, ++n)
      {
	if(ii == n)
	{ A = itr->second; }
	if(jj == n)
	{ B = itr->second; }
      }

      int kk = rand() % ( A.size() < B.size() ? A.size() : B.size());

      std::vector<int> child_A, child_B;

      for(int i = 0; i < kk; ++i)
      { child_A.push_back(A[i]); }
      for(int i = kk; i < B.size(); ++i)
      { child_A.push_back(B[i]); }	

      for(int i = 0; i < kk; ++i)
      { child_B.push_back(B[i]); }
      for(int i = kk; i < A.size(); ++i)
      { child_B.push_back(A[i]); }

      double rnd = (double) rand() / RAND_MAX;
      if(rnd < 0.2)
      { 
	int ll = rand() % child_A.size();
	if(ll > 0)
	{
	  int pp = rand() % nodes.size();
	  child_A[ll] = pp; 
	}
      }
      rnd = (double) rand() / RAND_MAX;
      if(rnd < 0.2)
      { 
	int ll = rand() % child_B.size();
	if(ll > 0)
	{
	  int pp = rand() % nodes.size();
	  child_B[ll] = pp; 
	}
      }

      std::vector<int> route_A, route_B;
      error = createRoute(child_A, route_A);
      error = createRoute(child_B, route_B);

      double scoreA, scoreB;

      scoreA = GetScoreRoute2(route_A); 
      scoreB = GetScoreRoute2(route_B);

      for(int p = 0; p < 1; ++p)
      {
	auto oldA = child_A, oldB = child_B;

	int ii_A = rand() % child_A.size(), jj_A = rand() % child_A.size();
	int ii_B = rand() % child_B.size(), jj_B = rand() % child_B.size();

	if(ii_A != 0 && jj_A != 0)
	{
	  int dummy = child_A[jj_A];
	  child_A[jj_A] = child_A[ii_A];
	  child_A[ii_A] = dummy;

	  if(0 < ii_A && ii_A < child_A.size())
	  { 
	    if(child_A[ii_A] == child_A[ii_A - 1] && child_A[ii_A] != 0)
	    { child_A.erase(child_A.begin() + ii_A); }
	    if(child_A[ii_A] == child_A[ii_A + 1] && child_A[ii_A] != 0)
	    { child_A.erase(child_A.begin() + ii_A); }
	  }
	  if(0 < jj_A && jj_A < child_A.size())
	  { 
	    if(child_A[jj_A] == child_A[jj_A - 1] && child_A[jj_A] != 0)
	    { child_A.erase(child_A.begin() + jj_A); }
	    if(child_A[jj_A] == child_A[jj_A + 1] && child_A[jj_A] != 0)
	    { child_A.erase(child_A.begin() + jj_A); }
	  }


	  std::vector<int> tmpRoute;
	  error = createRoute(child_A, tmpRoute);
	  double scoreA_test = GetScoreRoute2(tmpRoute);

	  if(scoreA_test < scoreA)
	  { child_A = oldA; }
	  else 
	  { scoreA = scoreA_test; }
	}

	if(ii_B != 0 && jj_B != 0)
	{
	  int dummy = child_B[jj_B];
	  child_B[jj_B] = child_B[ii_B];
	  child_B[ii_B] = dummy;


	  if(0 < ii_B && ii_B < child_B.size())
	  { 
	    if(child_B[ii_B] == child_B[ii_B - 1] && child_B[ii_B] != 0)
	    { child_B.erase(child_B.begin() + ii_B); }
	    if(child_B[ii_B] == child_B[ii_B + 1] && child_B[ii_B] != 0)
	    { child_B.erase(child_B.begin() + ii_B); }
	  }
	  if(0 < jj_B && jj_B < child_B.size())
	  { 
	    if(child_B[jj_B] == child_B[jj_B - 1] && child_B[jj_B] != 0)
	    { child_B.erase(child_B.begin() + jj_B); }
	    if(child_B[jj_B] == child_B[jj_B + 1] && child_B[jj_B] != 0)
	    { child_B.erase(child_B.begin() + jj_B); }
	  }

	  std::vector<int> tmpRoute;
	  error = createRoute(child_B, tmpRoute);
	  double scoreB_test = GetScoreRoute2(tmpRoute);

	  if(scoreB_test < scoreB)
	  { child_B = oldB; }
	  else 
	  { scoreB = scoreB_test; }
	}
      }
      routeNodesMap[-scoreA] = child_A;
      routeNodesMap[-scoreB] = child_B;

      if(scoreA > maxVal) { maxVal = scoreA; }
      if(scoreB > maxVal) { maxVal = scoreB; }

      std::map<double, std::vector<int>> tmpMap;
      n = 0;
      for(auto itr = routeNodesMap.begin(); itr != routeNodesMap.end(); ++itr, ++n)
      { 
	if(n == N) break;
	tmpMap[itr->first] = itr->second;
      }

      routeNodesMap = tmpMap;

      end = clock();
      double time = static_cast<double>((end - start) / CLOCKS_PER_SEC);
      if(time > 28)
      { break; }

      //cout << "best score is " << maxVal << ", " << time << endl;

    }

    error = createRoute(routeNodesMap.begin()->second, ansBestRoute);	
    //ansBestRoute = routeNodesMap.begin()->second;
#if 0
    sleep(100);


    for(int iloop = 0; iloop < 1000; ++iloop)
    {
      int ii = rand() % routeNodes.size(), jj = rand() % routeNodes.size();

      if(ii == 0 || jj == 0)
      { continue; }
#if 1
      int dummy = routeNodes[jj];
      routeNodes[jj] = routeNodes[ii];
      routeNodes[ii] = dummy;
#endif

      int ii2 = ii < jj ? ii : jj;
      int jj2 = ii < jj ? jj : ii;

      int kk = rand() % routeNodes.size();
      int ll = rand() % nodes.size() - 1;
      double rnd = (double) rand() / RAND_MAX;

      if(rnd < 0.2)
      { 
	if(ll == -1 && kk != 0)
	{  routeNodes.erase(routeNodes.begin() + kk); }
	else 
	{ routeNodes.insert(routeNodes.begin() + kk, 0); }
      } 
      std::vector<int> tmpNodes;
#if 0
      for(int i2 = 0; i2 < ii2; ++i2)
      { tmpNodes.push_back(routeNodes[i2]); }
      for(int i2 = jj2; i2 >= ii2; --i2)
      { tmpNodes.push_back(routeNodes[i2]); }
      for(int i2 = jj2 + 1; i2 < routeNodes.size(); ++i2)
      { tmpNodes.push_back(routeNodes[i2]); }
      routeNodes = tmpNodes;

#endif
      if(0 < ii && ii < routeNodes.size())
      { 
	if(routeNodes[ii] == routeNodes[ii - 1] && routeNodes[ii] != 0)
	{ routeNodes.erase(routeNodes.begin() + ii); }
	if(routeNodes[ii] == routeNodes[ii + 1] && routeNodes[ii] != 0)
	{ routeNodes.erase(routeNodes.begin() + ii); }
      }

      if(0 < jj && jj < routeNodes.size())
      { 
	if(routeNodes[jj] == routeNodes[jj - 1] && routeNodes[jj] != 0)
	{ routeNodes.erase(routeNodes.begin() + jj); }
	if(routeNodes[jj] == routeNodes[jj + 1] && routeNodes[jj] != 0)
	{ routeNodes.erase(routeNodes.begin() + jj); }
      }

      tmpRoute.clear();
      error = createRoute(routeNodes, tmpRoute);

      if(error !=  1)
      {
	double tmpval = GetScoreRoute2(tmpRoute);
	if(tmpval > maxVal)
	{ maxVal = tmpval; bestRouteNodes = routeNodes; ansBestRoute = tmpRoute; }
	else 
	{ routeNodes = bestRouteNodes; }

	cerr << tmpval << " " << nowTime << "  "<< maxVal << endl;
      }

      end = clock();
      double time = static_cast<double>((end - start) / CLOCKS_PER_SEC);

      if(time >= 28)
      { return error; }

    }
#endif
    //error = createRoute(routeNodes, tmpRoute);
    //cerr << GetScoreRoute2(ansBestRoute) << endl;
  }
  catch(std::exception e)
  {

  }

  return error;

}

int GatherOrder(std::vector<orderClass> &sOrders, std::vector<orderClass> &notDelivOrders, int t1, int t2)
{
  int error = 0;
  const int nOrderSize = orders.size();

  for(int i = 0; i < notDelivOrders.size(); ++i)
  { sOrders.push_back(notDelivOrders[i]); }
  notDelivOrders.clear();

  //gather orders t1~t2
  for(int t = t1; t <= t2; ++t)
  {
    if(t >= nOrderSize)
    { break;  }
    std::vector<orderClass> *tmpVec = &orders[t];

    for(int i = 0; i < tmpVec->size(); ++i)
    { sOrders.push_back(tmpVec->at(i)); }
  }
  //end gather

  if(sOrders.size() == 0)
  { error = 1; }
  return error;

}


int createFeasibleRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute)
{

  int error = 0;
  int thisNode = 0;
  const int nShuffle = 100;

  std::map<int, int> tmpMap;

  for(int i = 0; i < sOrders.size(); ++i)
  { tmpMap[sOrders[i].customer->index] = 0; }
  for(int i = 0; i < sOrders.size(); ++i)
  { tmpMap[sOrders[i].customer->index] += 1; }

  for(int i = 0; i < nShuffle; ++i)
  { 
    int ii = rand() % sOrders.size();
    int jj = rand() % sOrders.size();

    auto dummy = sOrders[jj];
    sOrders[jj] = sOrders[ii];
    sOrders[ii] = dummy;
  }

  bool fin = false;
  int iloop = 0;
  std::map<int, int> pathedMap;

  nodeClass *sNode = NULL, *eNode = NULL;
  sNode = &nodes[0];

  while(1)
  {
    if(iloop < sOrders.size())
    { 
      eNode = &nodes[sOrders[iloop].customer->index]; 

      if(pathedMap.find(eNode->index) != pathedMap.end())
      { ++iloop; continue; }
    }
    else 
    { eNode = &nodes[0]; fin = true; }

    std::vector<int> route = sNode->routeTo(eNode->index);

    for(int i = 0; i < route.size(); ++i)
    { 
      if(aRoute.size() > 0 && i == 0)
      { continue; }
      if(route[i] == 0 && aRoute.size() > 0)
      { fin = true; aRoute.push_back(route[i]); break;}
      aRoute.push_back(route[i]); 
    }
    for(int i = 0; i < route.size(); ++i)
    { pathedMap[route[i]] = 1; }

    if(fin) 
    { break; }
    sNode = eNode;
    ++iloop;
  }
  //end search route

  return error;
}

int ImproveTestRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute)
{

  int error = 0, nLoop = 10, iloop = 0;

  std::map<int, int> orderCounter, nodeCounter;
  std::map<int, std::vector<orderClass> > node2Orders;

  for(int i = 0; i < sOrders.size(); ++i)
  { 
    orderCounter[sOrders[i].customer->index] = 0; 
    node2Orders[sOrders[i].customer->index].clear();
  } 
  for(int i = 0; i < sOrders.size(); ++i)
  { 
    orderCounter[sOrders[i].customer->index] += 1; 
    node2Orders[sOrders[i].customer->index].push_back(sOrders[i]);
  }

  //search improved routing plan 
  while(iloop < nLoop)
  {

    ++iloop;
    bool fin = false;
    double maxDist = -1.0e16, maxCost = 0;
    int iroute = 0;
    int targetNode= 0, targetNode_next = 0;
    std::map<int, int> pathed;

    for(int ir = 0; ir < aRoute.size() - 1; ++ir)
    {
      if(aRoute[ir] == aRoute[ir + 1])
      { aRoute.erase(aRoute.begin() + ir + 1); }
    }

    for(int ir = 0; ir < aRoute.size(); ++ir)
    {
      if(ir>= aRoute.size() - 3)
      { break; }
      int node0 = aRoute[ir], node1 = aRoute[ir + 1], node2 = aRoute[ir + 2], node3 = aRoute[ir + 3];

      double dist01 = GetDist(node0, node1), dist23 = GetDist(node2, node3);
      double dist02 = GetDist(node0, node2), dist13 = GetDist(node1, node3);
      double dist12 = GetDist(node1, node2);

      //if(dist01 + dist23 > dist02 + dist13)
      { 
	if(maxDist < dist01 + dist23 - dist02 - dist13)
	{
	  targetNode = ir + 1;
	  targetNode_next = ir + 2;
	  maxDist = dist01 + dist23 - dist02 - dist13;
	}
      }

      double dS = 0.0;
      if(orderCounter.find(node1) != orderCounter.end() &&  pathed.find(node1) == pathed.end())
      {
	auto tmpvec = node2Orders[node1];
	for(int i = 0; i < tmpvec.size(); ++i)
	{ dS += tmpvec[i].dScore(dist01, dist02 + dist12); }
      }
      if(orderCounter.find(node2) != orderCounter.end() && pathed.find(node2) == pathed.end())
      {
	auto tmpvec = node2Orders[node2];
	for(int i = 0; i < tmpvec.size(); ++i)
	{ dS += tmpvec[i].dScore(dist01 + dist12, dist02); }
      }
      if(orderCounter.find(node3) != orderCounter.end() && pathed.find(node3) == pathed.end())
      {
	auto tmpvec = node2Orders[node3];
	for(int i = 0; i < tmpvec.size(); ++i)
	{ dS += tmpvec[i].dScore(dist01 + dist12 + dist23, dist02 + dist12 + dist13); }		   
      }
      if(dS > maxCost)
      {
	maxCost = dS;
	targetNode = ir+1 ;
	targetNode_next = ir+2;
      }
      pathed[node0] = node0;
    }

    if(maxDist > 1.0e-6 || maxCost > 1.0e-6 )
    {

      int dummy = aRoute[targetNode_next];
      aRoute[targetNode_next] = aRoute[targetNode];
      aRoute[targetNode] = dummy;
    }
    //end

    nodeCounter.clear();
    for(int ir = 0; ir < aRoute.size(); ++ir)
    { nodeCounter[aRoute[ir]] = 0; }
    for(int ir = 0; ir < aRoute.size(); ++ir)
    { nodeCounter[aRoute[ir]] += 1; }

    //erase edges
    if(true)
    {
      for(int ir = 0; ir < aRoute.size() - 1; ++ir)
      { 
	//auto itr_next = std::next(itr, 1);
	int node_this = aRoute[ir]; 
	int node_next = aRoute[ir + 1];
	//auto itr_skip = itr_next;
	int eraseIdx= ir + 1;

	int nCnt = nodeCounter[node_this];
	int oCnt = orderCounter.find(node_this) != orderCounter.end() ? orderCounter[node_this] : 0;
	int nCntNext = nodeCounter[node_next];
	int oCntNext = orderCounter.find(node_next) != orderCounter.end() ? orderCounter[node_next] : 0;

	if((nCntNext- oCntNext >= 1 || oCntNext == 0) ) 
	{ 
	  std::map<int, int> tmpNodeCounter = nodeCounter;

	  for(int ir2 = ir + 1; ir2 < aRoute.size() - 1; ++ir2)
	  {
	    int idx = aRoute[ir2];
	    int nCntNext2 = tmpNodeCounter[idx];
	    int oCntNext2 = orderCounter.find(idx) != orderCounter.end() ? orderCounter[idx] : 0;
	    double tmpDist = GetDist(node_this, aRoute[eraseIdx + 1]);
	    if(tmpDist < 1e+6)
	    {
	      eraseIdx = ir2; 
	    }

	    --tmpNodeCounter[idx];

	  }

	  int testNodeIdx = eraseIdx;

	  if(testNodeIdx >= aRoute.size() - 1)
	  { break; }
	  if(eraseIdx == ir + 1)
	  { continue; }

	  for(int ir2 = ir + 1; ir2 < eraseIdx; ++ir2)
	  { nodeCounter[aRoute[ir2]]--; }
	  aRoute.erase(aRoute.begin() + ir + 1, aRoute.begin() + eraseIdx);

	}
      }
    }
    //end

  }

  return error;

}

int SearchRoute(std::vector<orderClass> &sOrders, std::vector<orderClass> &notDelivOrders, double &score, std::vector<int> &aRouteEdge)
{
  int error = 0;
  int nRoute = 1;
  std::vector<std::vector<int> > routeList;
  std::map<int, std::vector<std::vector<int> > > sortedRouteMap;
  std::vector<int> bestRoute;

  double maxval = -1.0e+16;
  double minval = 1.0e+16;
  double dist = 0.0;
  int iRoute = -1;

  //0 - 0までの経路で一旦案を作成
  for(int i = 0; i < nRoute; ++i)
  {
    std::vector<int> aRoute;
    error = createFeasibleRoute(sOrders, aRoute);
    routeList.push_back(aRoute);
  }

  for(int i = 0; i < routeList.size(); ++i)
  { 
    double score = GetScoreRoute(sOrders, routeList[i]);
    double tmpdist = GetRouteDist(routeList[i]);
    if(score > maxval && tmpdist < 1e6)
    { 
      iRoute = i;
      maxval = score;
      dist = tmpdist; 
      minval = dist;
      bestRoute = routeList[i];
    }
  }

  std::map<int, std::vector<int> > orderIdxMap;

  for(int i = 0; i < sOrders.size(); ++i)
  { 
    int idx = sOrders[i].customer->index;
    orderIdxMap[idx].push_back(i);
  }

  for(int i = 0; i < bestRoute.size(); ++i)
  {
    int idx = bestRoute[i]; 
    if(orderIdxMap.find(idx) == orderIdxMap.end())
    { continue; }
    //orderIdxMap[idx] = -1;
    std::vector<int> tmpvec = orderIdxMap[idx];
    for(int j = 0; j < tmpvec.size(); ++j)
    { orderIdxMap[idx][j] = -1; }
  }

  for(auto itr = orderIdxMap.begin(); itr != orderIdxMap.end(); ++itr)
  {
    std::vector<int> *tmpvec = &itr->second;

    for(int j = 0; j < tmpvec->size(); ++j)
    {
      int idx = tmpvec->at(j);
      if(idx == -1)
      { continue; }
      notDelivOrders.push_back(sOrders[idx]);
    }
  }

  aRouteEdge = bestRoute;
  nowTime += dist;
  score = maxval;

  return error;
}

double GetRouteDist(std::vector<int> &aRoute)
{
  double dist_tot = 0;
  for(int i  = 0; i < aRoute.size() - 1; ++i)
  {
    dist_tot += GetDist(aRoute[i], aRoute[i + 1]);
  }
  return (dist_tot);
}

double GetScoreRoute2(std::vector<int> &aRoute)
{
  double score = 0.0; 
  int dt = 0;
  const int nOrderSize = orders.size();

  int lastStoreTime = 0;
  std::map<int, std::vector<orderClass*> > node2Orders;

  for(int i = 0; i < aRoute.size() - 1; ++i)
  {
    //arrive store
    if(aRoute[i] == 0)
    {

      for(int t = lastStoreTime ; t <= dt; ++t)
      {
	if(t >= nOrderSize)
	{ continue; }
	std::vector<orderClass> *tmpVec = &orders[t];

	for(int j = 0; j < tmpVec->size(); ++j)
	{ 
	  tmpVec->at(j).done = false;
	  node2Orders[tmpVec->at(j).customer->index].push_back(&tmpVec->at(j)); 
	}
      }	
      lastStoreTime = dt + 1;
    }

    if(node2Orders.find(aRoute[i]) != node2Orders.end())
    {
      std::vector<orderClass*> *ordervec = &node2Orders[aRoute[i]]; 
      for(int j = 0; j < ordervec->size(); ++j)
      {
	orderClass *aOrder = ordervec->at(j);

	if(aOrder->done) 
	{ continue; }

	if(dt >= Tmax)
	{ continue; }

	double arrivalTime = dt, aOrderTime = aOrder->ordertime;
	double waitTime = arrivalTime - aOrderTime;

	aOrder->done = true;

	score += Tmax * Tmax - waitTime * waitTime;
      }
    }

    dt += GetDist( aRoute[i], aRoute[i + 1] );

    if(dt >= 1e+6)
    { return 0.0; }

    if(aRoute[i] == aRoute[i + 1]) 
    { dt += 1; }

    if(dt >= Tmax)
    { break; }
  }


  nowTime = dt;

  return score;
}

double GetScoreRoute(std::vector<orderClass> &sOrders, std::vector<int> &aRoute)
{
  double score = 0, dt = nowTime;
  std::map<int, int> nodeArriaValTime;
  for(int i = 0; i < aRoute.size() - 1; ++i)
  {
    if(aRoute[i] == aRoute[i + 1])
    { dt += 1; }
    else 
    { dt += GetDist(aRoute[i], aRoute[i+1]); }
    if(nodeArriaValTime.find(aRoute[i+1]) == nodeArriaValTime.end())
    { nodeArriaValTime[aRoute[i+1]] = dt;}
  }

  for(int i = 0; i < sOrders.size(); ++i)
  {
    if(nodeArriaValTime.find(sOrders[i].customer->index) == nodeArriaValTime.end())
    { continue; }
    double arrivalTime = nodeArriaValTime[sOrders[i].customer->index]; 
    double orderTime = sOrders[i].ordertime;	
    double waitingTime = arrivalTime - orderTime;
    score += Tmax * Tmax - waitingTime * waitingTime;
  }

  return (score);

}

double orderClass::dScore(double dt1, double dt2)
{ return -(dt1 - dt2) * (-2 * nowTime + 2 * this->ordertime - dt1 - dt2); } 

int Dikstra(int fromIdx, int toIdx)
{
  for(int i = 0; i < nodes.size(); ++i)
  { 
    nodes[i].done = false;
    nodes[i].cost = -1;
    nodes[i].preIdx = nodes[i].nextIdx = -1;
  }    

  nodes[fromIdx].cost= 0;

  while(true)
  {
    nodeClass *aProcNode = NULL;

    for(int i = 0; i < nodes.size(); ++i)
    {
      nodeClass *aNode = &nodes[i];

      if(aNode->done || aNode->cost < 0)
      { continue; }

      if(aProcNode == NULL)
      { aProcNode = aNode; continue; }

      if(aNode->cost < aProcNode->cost)
      { aProcNode  = aNode; }
    }

    if(aProcNode == NULL)
    { break; }

    aProcNode->done = true;

    std::vector<edgeClass> tmpEdgeVec = edges[aProcNode->index];

    for(int i = 0; i < tmpEdgeVec.size(); ++i)
    {
      edgeClass *aEdge = &tmpEdgeVec[i];
      nodeClass *aNode = &nodes[aEdge->to->index];

      double cost = aProcNode->cost + aEdge->dist;
      bool update = (aNode->cost < 0) || (aNode->cost > cost);

      if(update)
      {
	aNode->cost = cost;
	aNode->preIdx = aProcNode->index;
	aProcNode->nextIdx = aNode->index;
      }
    }

  }

  for(int i = 0; i < nodes.size(); ++i)
  { 
    nodeClass aNode;
    aNode.index = nodes[i].index;
    aNode.done = nodes[i].done;
    aNode.preIdx = nodes[i].preIdx;
    aNode.nextIdx = nodes[i].nextIdx;
    aNode.cost = nodes[i].cost;
    //nodes[fromIdx].optRouteInfo = nodes;
    nodes[fromIdx].optRouteInfo.push_back(aNode);
  }

  if(toIdx < 0)
  { return 0; }

  nodeClass *currentNode = &nodes[toIdx];

  while(true)
  {
    nodeClass *nextNode = &nodes[currentNode->preIdx];

    if(nextNode == NULL || nextNode->index == fromIdx)
    { break; }	   
    currentNode = nextNode;

  }

  return 0;
}

std::vector<int> nodeClass::routeTo(int toIdx)
{

  if(this->routeToMap.find(toIdx) != this->routeToMap.end())
  { return this->routeToMap[toIdx]; }

  std::vector<int> rvec, tmpvec;
  nodeClass *currentNode = &optRouteInfo[toIdx];

  tmpvec.push_back(currentNode->index);

  while(true)
  {
    nodeClass *nextNode = &optRouteInfo[currentNode->preIdx];

    if(nextNode != NULL)
    { tmpvec.push_back(nextNode->index); }
    if(nextNode == NULL || nextNode->index == this->index)
    { break; }	   
    currentNode = nextNode;
  }

  for(int i = tmpvec.size() - 1; i >= 0; --i)
  { rvec.push_back(tmpvec[i]); }

  routeToMap[toIdx] = rvec;

  return rvec;
}

/*
   for(auto itr = sortedRouteMap.begin(); itr != sortedRouteMap.end(); ++itr)
   { 
   auto vec = itr->second;

   for(int i = 0; i < vec.size(); ++i)
   { routeList.push_back(vec[i]); }

   if(routeList.size() > 50)
   { break; }
   }
 */

void displayRoute(std::vector<int> &aRoute)
{

  cerr << "route => ";
  for(int i = 0; i < aRoute.size(); ++i)
  { cerr << aRoute[i] << " " ; }
  cerr << endl;

  return;
}

int createRoute(std::vector<int> &pathNodes, std::vector<int> &aRoute)
{

  int error = 0;

  std::map<int, int> pathedMap;
  int nodeIdx_from = 0, nodeIdx_to = 0;

  clock_t start = clock();

  for(int i = 0; i < pathNodes.size() - 1; ++i)
  {
    int k = i + 1;
    nodeIdx_from = pathNodes[i];
    nodeIdx_to = pathNodes[k];

    if(pathedMap.find(nodeIdx_to) != pathedMap.end())
    {
      int l;
      for(l = i + 2; l < pathNodes.size(); ++l)
      {
	nodeIdx_to = pathNodes[l];
	if(pathedMap.find(nodeIdx_to) == pathedMap.end())
	{ break; }
      }
      i = l - 1;
    }

    if(nodeIdx_from == 0)
    { pathedMap.clear(); }

    if(nodeIdx_from == nodeIdx_to && nodeIdx_from == 0)
    { aRoute.push_back(0); continue; }

    if(nodeIdx_from == 0 || nodeIdx_from != nodeIdx_to)
    {
      std::vector<int> tmpRoute = nodes[nodeIdx_from].routeTo(nodeIdx_to);
      for(int j = 0; j < tmpRoute.size(); ++j)
      {
	if(j < tmpRoute.size() - 1)
	{ aRoute.push_back(tmpRoute[j]); }

	if(j < tmpRoute.size() - 1 && tmpRoute[j] != 0)
	{ pathedMap[tmpRoute[j]] = 1; }
      }
    }

  }


  return error;

}


void outputRoute(std::vector<int> &aRoute)
{

  int preNode = 0;
  int time = 0;

  for(int i = 0; i < aRoute.size() - 1; ++i)
  {
    if(time >= Tmax)
    { break; }
    int thisNode = aRoute[i];

    if(thisNode == preNode)
    { 
      if(time < Tmax)
      { cout << "-1" << endl; } 
      ++time;
    }
    else 
    { 
      double dist = GetDist(preNode, thisNode);

      for(int j = 0; j < dist; ++j, ++time)
      { 
	if(time < Tmax)
	{ cout << thisNode + 1 << endl; }
      }
    }
    preNode = thisNode;

  }

  if(time < Tmax)
  { 
    for(int t = time; t < Tmax; ++t)
    { cout << "-1" << endl; }
  }

  return ;
}



Measured memory_bytes: 29648