#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <limits>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <time.h>
#include <sys/timeb.h>
using namespace std;

template<class F, class S> string in_v_to_str (const pair<F, S> v);
template<class F, class S> string v_to_str (const pair<F, S> v);
string in_v_to_str (const char v) { return "'" + string{v} + "'"; }
string in_v_to_str (const char* v) { return '"' + v + '"'; }
string in_v_to_str (const string v) { return '"' + v + '"'; }
template<class T> string in_v_to_str (const T v) { stringstream ss; ss << v; return ss.str(); }
template<class T> string v_to_str (const T v) { stringstream ss; ss << v; return ss.str(); }
template<class T, size_t N> string v_to_str (const array<T, N>& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (int i = 0; i < v.size() - 1; ++i) { ss << in_v_to_str(v[i]) << ", "; } ss << in_v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[]"; } return ss.str(); }
template<class T, size_t N> string v_to_str (const array< array<T, N>, N >& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (int i = 0; i < v.size() - 1; ++i) { ss << v_to_str(v[i]) << ", "; } ss << v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[-]"; } return ss.str(); }
template<class T> string v_to_str (const vector<T>& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (int i = 0; i < v.size() - 1; ++i) { ss << in_v_to_str(v[i]) << ", "; } ss << in_v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[]"; } return ss.str(); }
template<class T> string v_to_str (const vector< vector<T> >& v) { stringstream ss; if (v.size() > 0) { ss << "["; for (int i = 0; i < v.size() - 1; ++i) { ss << v_to_str(v[i]) << ", "; } ss << v_to_str(v[v.size() - 1]) << "]"; } else { ss << "[-]"; } return ss.str(); }
template<class T> string v_to_str (const set<T>& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i) << (len-- > 1 ? ", " : "}"); } return ss.str(); }
template<class K, class V> string v_to_str (const map<K, V>& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i.first) << " : " << in_v_to_str(i.second) << (len-- > 1 ? ", " : "}"); } return ss.str(); }
template<class T> string v_to_str (const unordered_set<T>& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i) << (len-- > 1 ? ", " : "}"); } return ss.str(); }
template<class K, class V> string v_to_str (const unordered_map<K, V>& v) { stringstream ss; int len = v.size(); ss << (v.size() > 0 ? "{" : "{}"); for (auto& i : v) { ss << in_v_to_str(i.first) << " : " << in_v_to_str(i.second) << (len-- > 1 ? ", " : "}"); } return ss.str(); }
template<class F, class S> string in_v_to_str (const pair<F, S> v) { stringstream ss; ss << "<" << v_to_str(v.first) << ", " << v_to_str(v.second) << ">"; return ss.str(); }
template<class F, class S> string v_to_str (const pair<F, S> v) { stringstream ss; ss << "<" << v_to_str(v.first) << ", " << v_to_str(v.second) << ">"; return ss.str(); }
string print () { return ""; }
template<typename F, typename... R> string print (const F& f, const R& ...r) { stringstream ss; ss << v_to_str(f); if (sizeof...(r) > 0) { ss << " " << print(r...); } return ss.str(); }

template<typename F, typename... R> void pdebug (const F& f, const R& ...r) {
    stringstream ss;
    ss << v_to_str(f); if (sizeof...(r) > 0) { ss << " " << print(r...); }
    cerr << "<cerr>" << ss.str() << "</cerr>" << endl;
}

template<typename F, typename... R> void fdebug (const F& f, const R& ...r) {
    stringstream ss;
    ss << v_to_str(f); if (sizeof...(r) > 0) { ss << " " << print(r...); }
    cerr << "<cerrfile>" << ss.str() << "</cerrfile>" << endl;
}

class StopWatch {
public:
    int starts;
    int startm;
    int tstarts = 0;
    int tstartm = 0;
    struct timeb timebuffer;
    StopWatch () {
        ftime(&this->timebuffer);
        this->starts = this->timebuffer.time;
        this->startm = this->timebuffer.millitm;
    }
    inline void stop () {
        ftime(&this->timebuffer);
        this->tstarts = this->timebuffer.time;
        this->tstartm = this->timebuffer.millitm;
    }
    inline void resume () {
        ftime(&this->timebuffer);
        this->starts += this->timebuffer.time - this->tstarts;
        this->startm += this->timebuffer.millitm - this->tstartm;
    }
    inline int get_milli_time () {
        ftime(&this->timebuffer);
        return (this->timebuffer.time - this->starts) * 1000 + (this->timebuffer.millitm - this->startm);
    }
};

struct e512pos {
public:
    int x;
    int y;
    e512pos () { this->x = 0; this->y = 0; }
    e512pos (int x, int y) {
        this->x = x;
        this->y = y;
    }
    e512pos operator + (const e512pos& t) { return e512pos(this->x + t.x, this->y + t.y); }
    e512pos operator - (const e512pos& t) { return e512pos(this->x - t.x, this->y - t.y); }
    bool operator == (const e512pos& t) const { return this->x == t.x && this->y == t.y; }
};

namespace std {
    template <> class hash<e512pos> {
    public:
        size_t operator()(const e512pos& t) const{ return hash<int>()(t.x<<16) | hash<int>()(t.y); }
    };
}

inline uint32_t xrnd() {
    static uint32_t y = 2463534242;
    y = y ^ (y << 13);
    y = y ^ (y >> 17);
    return y = y ^ (y << 5);
}

inline double distance (const double& ax, const double& ay, const double& bx, const double& by) {
    return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
}
inline double distance (const int& ax, const int& ay, const int& bx, const int& by) {
    return sqrt((ax - bx) * (ax - bx) + (ay - by) * (ay - by));
}
inline float distance (const e512pos& a, const e512pos& b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

struct Edge {
public:
    int a, b, cost;
    Edge () {
        this->a = 0;
        this->b = 0;
        this->cost = 1000000;
    }
    Edge (int a, int b, int cost) {
        this->a = a;
        this->b = b;
        this->cost = cost;
    }
    bool operator == (const Edge& t) const { return this->a == t.a && this->b == t.b; }
};
namespace std {
    template <> class hash<Edge> {
    public:
        size_t operator()(const Edge& t) const{ return hash<int>()(t.a<<16) | hash<int>()(t.b); }
    };
}

class GraphDijkstra {
private:
    class Node {
    public:
        int cost;
        int index;
        Node (int cost, int index) {
            this->cost = cost;
            this->index = index;
        }
        bool operator > (const Node& t) const { return this->cost > t.cost; }
        bool operator < (const Node& t) const { return this->cost < t.cost; }
    };
    int tmp = -1;
    vector<int> prevs;
    vector<int> costs;
    priority_queue<Node, vector<Node>, greater<Node> > que;
    vector< vector< pair<int, int> > > edgecost;
public:
    int n;
    vector<int> path;
    vector<int> rpath;
    int pathcost;
    GraphDijkstra () {};
    GraphDijkstra (int n, vector<Edge> edges, bool undir = false) {
        this->pathcost = 0;
        this->path.clear();
        this->n = n;
        this->edgecost = vector< vector< pair<int, int> > >(this->n, vector< pair<int, int> >());
        if (undir) {// undirected
            for (auto&& i : edges) {
                this->edgecost[i.a].emplace_back(i.b, i.cost);
                this->edgecost[i.b].emplace_back(i.a, i.cost);
            }
        } else {// directed
            for (auto&& i : edges) {
                this->edgecost[i.a].emplace_back(i.b, i.cost);
            }
        }
    }
    
    GraphDijkstra (vector<Edge> edges, bool undir = false) {
        this->pathcost = 0;
        this->path.clear();
        int n = 0;
        for (auto&& i : edges) { n = max(max(i.a, i.b), n); }
        this->n = n+1;
        this->edgecost = vector< vector< pair<int, int> > >(this->n, vector< pair<int, int> >());
        if (undir) {// undirected
            for (auto&& i : edges) {
                this->edgecost[i.a].emplace_back(i.b, i.cost);
                this->edgecost[i.b].emplace_back(i.a, i.cost);
            }
        } else {// directed
            for (auto&& i : edges) {
                this->edgecost[i.a].emplace_back(i.b, i.cost);
            }
        }
    }
    
    void calcPath (int start_i, int end_i) {
        static const int limit = numeric_limits<int>::max();
        this->path.clear();
        this->rpath.clear();
        if (this->tmp != start_i) {
            this->prevs = vector<int>(this->n, -1);
            this->costs = vector<int>(this->n, limit);
            this->que = priority_queue<Node, vector<Node>, greater<Node> >();
            this->costs[start_i] = 0;
            this->que.emplace(0, start_i);
        }
        this->tmp = start_i;
        
        while (!this->que.empty()) {
            const Node t = this->que.top();
            if (t.cost >= this->costs[end_i]) { break; }
            this->que.pop();
            for (auto&& i : this->edgecost[t.index]) {
                const int cost = t.cost + i.second;
                if (cost < this->costs[i.first]) {
                    this->costs[i.first] = cost;
                    this->prevs[i.first] = t.index;
                    this->que.emplace(cost, i.first);
                }
            }
        }
        
        if (this->costs[end_i] < limit) {
            this->pathcost = this->costs[end_i];
            int e = end_i;
            while (e > -1) {
                this->rpath.emplace_back(e);
                e = this->prevs[e];
            }
            this->path = this->rpath;
            reverse(this->path.begin(), this->path.end());
        } else {
            this->pathcost = -1;
        }
    }
};

vector<Edge> gridToGraph (vector< vector<int> >& grid) {
    static const int dx[4] = {0, 0, -1, 1};
    static const int dy[4] = {-1, 1, 0, 0};
    
    vector<Edge> r;
    int h = grid.size();
    int w = grid[0].size();
    for (int y = 0; y < h; ++y) {
        for (int x = 0; x < w; ++x) {
            int ax = x;
            int ay = y;
            for (int i = 0; i < 4; ++i) {
                int bx = ax + dx[i];
                int by = ay + dy[i];
                if (bx < 0 || bx >= w || by < 0 || by >= h) { continue; }
                r.emplace_back(Edge(ay*w+ax, by*w+bx, grid[by][bx]));
            }
        }
    }
    return r;
}

class Order {
public:
    int t;
    int new_id;
    int dst;
    Order () {}
    Order (int t, int new_id, int dst) {
        this->t = t;
        this->new_id = new_id;
        this->dst = dst;
    }
};
ostream& operator << (ostream& os, const Order& p) {
    os << "(" << p.t << ", " << p.new_id << ", " << p.dst << ")";
    return os;
}

class MM {
public:
    StopWatch sw;
    int V, E;
    int TMax;
    vector<Edge> G;
    vector<Order> orders;
    vector<Order> baseorder;
    int costs[405][405];
    int pathcosts[405][405];
    vector< vector<int> > baggages;
    
    
    
    int ordercnt[405];
    
    GraphDijkstra g;
    MM () {
        this->sw = StopWatch();
        cin >> this->V >> this->E;
        
        for (int i = 0; i < this->E; ++i) {
            Edge e;
            cin >> e.a >> e.b >> e.cost;
            this->costs[e.a][e.b] = e.cost;
            this->costs[e.b][e.a] = e.cost;
            this->G.emplace_back(e);
        }
        cin >> this->TMax;
        
        
        for (int i = 0; i < 405; ++i) { this->ordercnt[i] = 0; }
        
        for (int i = 0; i < this->TMax; ++i) {
            int t;
            cin >> t;
            if (t) {
                Order o;
                o.t = i;
                cin >> o.new_id >> o.dst;
                this->orders.emplace_back(o);
                this->ordercnt[o.dst] += 1;
            } else {
                Order o;
                o.t = i;
                o.new_id = -1;
                o.dst = -1;
                this->orders.emplace_back(o);
            }
        }
        
        this->g = GraphDijkstra(405, this->G, true);
        for (int i = 0; i < 405; ++i) {
            for (int j = i+1; j < 405; ++j) {
                this->g.calcPath(j, i);
                if (this->g.pathcost < 0) {
                    this->pathcosts[j][i] = 1000;
                    this->pathcosts[i][j] = 1000;
                } else {
                    this->pathcosts[j][i] = this->g.pathcost;
                    this->pathcosts[i][j] = this->g.pathcost;
                }
            }
        }
        
        
        
        
        int bestscore = 0;
        vector<int> bestoutputcommand;
        
        for (int i = 0; i < 405; ++i) { this->baggages.emplace_back(vector<int>()); }
        while (this->sw.get_milli_time() < 29500) {
            
            for (int z = 0; z < 405; ++z) { this->baggages[z].clear(); }
            this->baseorder.clear();
            int64_t score = 0;
            vector<int> outputcommand;
            vector<int> command;
            bool ishome = true;
            int pos = 1;
            int movecnt = 0;
            int nextpos = -1;
            uint64_t cnt = 0;
            bool f = true;
            int endcnt = 32 + xrnd() % 64;
            
            for (int i = 0; i < this->TMax; ++i) {
                
                if (this->orders[i].new_id > -1) {
                    this->baseorder.emplace_back(this->orders[i]);
                }
                
                
                vector<int> orientation;
                orientation.emplace_back(1);
                
                if (movecnt == 0 && nextpos > 0) { pos = nextpos; }
                ishome = (pos == 1 && movecnt == 0);
                if (ishome) {
                    for (auto&& o : this->baseorder) {
                        this->baggages[o.dst].emplace_back(o.t);
                    }
                    for (int z = 0; z < 405; ++z) {
                        if (this->baggages[z].size() > 0) {
                            orientation.emplace_back(z);
                        }
                    }
                    this->baseorder.clear();
                } else {
                    if (movecnt == 0) {
                        cnt += this->baggages[pos].size();
                        const int64_t maxpoint = this->TMax * this->TMax;
                        for (auto&& t : this->baggages[pos]) {
                            int64_t d = i - t;
                            score += maxpoint - d*d;
                        }
                        this->baggages[pos].clear();
                    }
                }
                
                
                orientation.emplace_back(1);
                
                
                if (orientation.size() > 2) {
                    command.clear();
                    auto tmp = orientation;
                    int bestdist = 1000000; 
                    
                    
                    // if (i < 6000) {
                    //     endcnt = 300;
                    // }
                    
                    tmp = this->nearestNeighbor(tmp);
                    
                    for (int z = 0; z < 1; ++z) {
                        int dist = 0;
                        // shuffle(tmp.begin()+1, tmp.end()-1, mt19937(xrnd()));
                        auto torientation = this->orderDistSA(endcnt, tmp, dist);
                        if (dist < bestdist) {
                            orientation = torientation;
                            bestdist = dist;
                        }
                    }
                    
                    auto path = this->orientationToPath(orientation);
                    path = this->pathScoreSA(4, path, i);
                    int64_t pscorea = this->pathScore(path, i);
                    if (bestdist + i > this->TMax) {
                        auto orientationb = this->orientationPathScoreSA(2, orientation, i);
                        auto pathb = this->orientationToPath(orientationb);
                        pathb = this->pathScoreSA(4, pathb, i);
                        int64_t pscoreb = this->pathScore(pathb, i);
                        if (pscoreb > pscorea) { path = pathb; }
                    }
                    
                    
                    int p = 1;
                    for (int k = 0; k < path.size()-1; ++k) {
                        for (int z = 0; z < this->costs[p][path[k+1]]; ++z) {
                            command.emplace_back(path[k+1]);
                        }
                        p = path[k+1];
                    }
                    
                    reverse(command.begin(), command.end());
                    
                }
                
                if (movecnt == 0 && pos != 1 && this->baseorder.size() > 0) {
                    if (i > 8500 && this->baseorder.size()/this->pathcosts[pos][1] > 6) {
                        command.clear();
                        orientation.clear();
                        orientation.emplace_back(pos);
                        orientation.emplace_back(1);
                        auto path = this->orientationToPath(orientation);
                        int p = pos;
                        for (int k = 0; k < path.size()-1; ++k) {
                            for (int z = 0; z < this->costs[p][path[k+1]]; ++z) {
                                command.emplace_back(path[k+1]);
                            }
                            p = path[k+1];
                        }
                        
                        reverse(command.begin(), command.end());
                    } else if (i > 0 && this->baseorder.size()/this->pathcosts[pos][1] > 12) {
                        command.clear();
                        orientation.clear();
                        orientation.emplace_back(pos);
                        orientation.emplace_back(1);
                        auto path = this->orientationToPath(orientation);
                        int p = pos;
                        for (int k = 0; k < path.size()-1; ++k) {
                            for (int z = 0; z < this->costs[p][path[k+1]]; ++z) {
                                command.emplace_back(path[k+1]);
                            }
                            p = path[k+1];
                        }
                        
                        reverse(command.begin(), command.end());
                    }
                }
                
                
                
                
                if (command.size() > 0) {
                    // cout << command.back() << endl;
                    outputcommand.emplace_back(command.back());
                    if (nextpos != command.back()) {
                        nextpos = command.back();
                        movecnt = this->costs[pos][nextpos];
                    }
                    movecnt -= 1;
                    command.pop_back();
                } else {
                    // cout << -1 << endl;
                    outputcommand.emplace_back(-1);
                }
                
                //cout << -1 << endl;
                
                
                if (this->sw.get_milli_time() > 29500) {
                    f = false;
                    break;
                }
            }
            if (movecnt == 0 && nextpos > 0) { pos = nextpos; }
            ishome = (pos == 1 && movecnt == 0);
            if (movecnt == 0) {
                cnt += this->baggages[pos].size();
                const int64_t maxpoint = this->TMax * this->TMax;
                for (auto&& t : this->baggages[pos]) {
                    int64_t d = this->TMax - t;
                    score += maxpoint - d*d;
                }
                this->baggages[pos].clear();
            }
            
            if (f && score >= bestscore) {
                bestscore = score;
                bestoutputcommand = outputcommand;
            }
            
            
        }
        
        for (auto&& i : bestoutputcommand) {
            cout << i << endl;
        }
        
        // int mcnt = 0;
        // for (int i = 0; i < 405; ++i) { mcnt += this->baggages[i].size(); }
        // int homecnt = 0;
        // for (auto&& i : this->baseorder) { homecnt += 1; }
        pdebug(this->V, this->E);
        pdebug("T", this->sw.get_milli_time());
        // pdebug(cnt, mcnt, homecnt);
        // pdebug(this->score);
    }
    
    
    vector<int> nearestNeighbor (const vector<int> v) {
        vector<int> r;
        vector<bool> f(405, false);
        f[1] = true;
        r.emplace_back(1);
        
        for (int i = 1; i < v.size()-1; ++i) {
            int best = 1;
            int bestdist = 1000000;
            for (int j = 1; j < v.size()-1; ++j) {
                if (f[j]) { continue; }
                int dist = this->pathcosts[r.back()][v[j]];
                if (dist < bestdist) {
                    bestdist = dist;
                    best = j;
                }
            }
            r.emplace_back(v[best]);
            f[best] = true;
        }
        
        r.emplace_back(1);
        return r;
    }
    
    
    vector<int> orientationToPath (vector<int> orientation) {
        vector<int> path;
        int p = orientation[0];
        
        path.emplace_back(p);
        for (int j = 1; j < orientation.size()-1; ++j) {
            this->g.calcPath(p, orientation[j]);
            for (int k = 1; k < this->g.path.size(); ++k) {
                path.emplace_back(this->g.path[k]);
            }
            p = orientation[j];
        }
        
        this->g.calcPath(p, 1);
        for (int k = 1; k < this->g.path.size(); ++k) {
            path.emplace_back(this->g.path[k]);
        }
        
        return path;
    }
    
    int64_t pathScore (const vector<int>& path, int turn) {
        int64_t score = 0;
        const int64_t maxpoint = this->TMax * this->TMax;
        int pos = path[0];
        int i = 1;
        bool b[405];
        for (int z = 0; z < 405; ++z) { b[z] = true; }
        while (turn <= this->TMax && i < path.size()) {
            turn += this->costs[pos][path[i]];
            if (turn <= this->TMax) {
                if (b[path[i]]) {
                    for (auto&& t : this->baggages[path[i]]) {
                        int64_t d = turn - t;
                        score += maxpoint - d*d;
                    }
                    b[path[i]] = false;
                }
            }
            pos = path[i];
            i += 1;
        }
        
        return score;
    }
    
    int64_t orientationPathScore (const vector<int>& path, int turn) {
        int64_t score = 0;
        const int64_t maxpoint = this->TMax * this->TMax;
        int pos = path[0];
        int i = 1;
        bool b[405];
        for (int z = 0; z < 405; ++z) { b[z] = true; }
        while (turn <= this->TMax && i < path.size()) {
            turn += this->pathcosts[pos][path[i]];
            if (turn <= this->TMax) {
                if (b[path[i]]) {
                    for (auto&& t : this->baggages[path[i]]) {
                        int64_t d = turn - t;
                        score += maxpoint - d*d;
                    }
                    b[path[i]] = false;
                }
            }
            pos = path[i];
            i += 1;
        }
        
        return score;
    }
    
    
    vector<int> orientationPathScoreSA (int end, vector<int> ret, int i) {
        vector<int> bestret = ret;
        int64_t bestscore = this->orientationPathScore(ret, i);
        int64_t lastscore = bestscore;
        
        int saTimeStart = 0;
        int saTimeEnd   = end;
        int64_t R = 1000000000;
        
        for (int z = 0; z < saTimeEnd; ++z) {
            for (int a = 1; a < ret.size()-2; ++a) {
                for (int b = a+1; b < ret.size()-1; ++b) {
                    swap(ret[a], ret[b]);
                    int64_t tmpscore = this->orientationPathScore(ret, i);
                    
                    const double T = saTimeEnd-saTimeStart;
                    const double t = z-saTimeStart;
                    const double startTemp   = 2.0;
                    const double endTemp     = 0.0;
                    const double temp        = startTemp + (endTemp - startTemp) * t / T;
                    const double probability = exp((tmpscore - lastscore) / temp);
                    const bool FORCE_NEXT    = probability > (double)(xrnd() % R) / R;
                    
                    if (tmpscore > lastscore || FORCE_NEXT) {
                        lastscore = tmpscore;
                        if (tmpscore > bestscore) {
                            bestscore = tmpscore;
                            bestret = ret;
                        }
                    } else {
                        swap(ret[a], ret[b]);
                    }
                }
            }
        }
        
        return bestret;
    }
    
    
    vector<int> pathScoreSA (int end, vector<int> ret, int i) {
        vector<int> bestret = ret;
        int64_t bestscore = this->pathScore(ret, i);
        int64_t lastscore = bestscore;
        
        int saTimeStart = 0;
        int saTimeEnd   = end;
        int64_t R = 1000000000;
        
        for (int z = 0; z < saTimeEnd; ++z) {
            for (int a = 0; a < ret.size()-2; ++a) {
                for (int b = ret.size()-1; b > a+1; --b) {
                    
                    if (ret[a] != ret[b]) { continue; }
                    reverse(ret.begin() + a, ret.begin() + b + 1);
                    
                    int64_t tmpscore = this->pathScore(ret, i);
                    
                    const double T = saTimeEnd-saTimeStart;
                    const double t = z-saTimeStart;
                    const double startTemp   = 2.0;
                    const double endTemp     = 0.0;
                    const double temp        = startTemp + (endTemp - startTemp) * t / T;
                    const double probability = exp((tmpscore - lastscore) / temp);
                    const bool FORCE_NEXT    = probability > (double)(xrnd() % R) / R;
                    
                    if (tmpscore > lastscore || FORCE_NEXT) {
                        lastscore = tmpscore;
                        if (tmpscore > bestscore) {
                            bestscore = tmpscore;
                            bestret = ret;
                        }
                    } else {
                        reverse(ret.begin() + a, ret.begin() + b + 1);
                    }
                }
            }
        }
        
        return bestret;
    }
    
    vector<int> orderDistSA (int limit, vector<int> ret, int& dist) {
        dist = this->orderDistScore(ret);
        if (ret.size() < 4) { return ret;}
        
        vector<int> bestret = ret;
        double bestscore = this->orderDistScore(ret);
        double lastscore = bestscore;
        int saTimeStart = 0;
        int saTimeEnd   = limit;
        int64_t R = 1000000000;
        
        for (int z = 0; z < saTimeEnd; ++z) {
            if (this->sw.get_milli_time() > 29500) { break; }
            for (int a = 1; a < ret.size()-2; ++a) {
                for (int b = a+1; b < ret.size()-1; ++b) {
                    
                    if (a == 1 && b == ret.size()-2) { continue; }
                    
                    double tmpscore = this->orderDiffDistScore(a, b, ret, lastscore);
                    
                    const double T = saTimeEnd-saTimeStart;
                    const double t = z-saTimeStart;
                    const double startTemp   = 2.0;
                    const double endTemp     = 0.0;
                    const double temp        = startTemp + (endTemp - startTemp) * t / T;
                    
                    const double probability = exp((lastscore - tmpscore) / temp);
                    const bool FORCE_NEXT    = probability > (double)(xrnd() % R) / R;
                    
                    if (tmpscore <= lastscore || FORCE_NEXT) {
                        lastscore = tmpscore;
                        reverse(ret.begin() + a, ret.begin() + b + 1);
                        if (tmpscore < bestscore) {
                            bestscore = tmpscore;
                            bestret = ret;
                        }
                    } else {
                        
                    }
                }
            }
            // if (ret.size() < 5) { continue; }
            // for (int i = 0; i < 128; ++i) {
            //     int a = xrnd() % (ret.size()-3)+1;
            //     int b = a + xrnd() % (ret.size()-2-a);
            //     int c = b + xrnd() % (ret.size()-1-b);
                
                
            //     reverse(ret.begin() + a, ret.begin() + b);
            //     reverse(ret.begin() + b, ret.begin() + c + 1);
            //     double tmpscore = this->orderDistScore(ret);
                    
            //     const double T = saTimeEnd-saTimeStart;
            //     const double t = z-saTimeStart;
            //     const double startTemp   = 2.0;
            //     const double endTemp     = 0.0;
            //     const double temp        = startTemp + (endTemp - startTemp) * t / T;
            //     const double probability = exp((lastscore - tmpscore) / temp);
            //     const bool FORCE_NEXT    = probability > (double)(xrnd() % R) / R;
                
            //     if (tmpscore <= lastscore || FORCE_NEXT) {
            //         lastscore = tmpscore;
                    
            //         if (tmpscore < bestscore) {
            //             bestscore = tmpscore;
            //             bestret = ret;
            //         }
            //     } else {
            //         reverse(ret.begin() + b, ret.begin() + c + 1);
            //         reverse(ret.begin() + a, ret.begin() + b);
            //     }
                
                
            // }
            
        }
        // fdebug(bestscore);
        dist = bestscore;
        return bestret;
    }
    
    double orderDistScore(const vector<int>& ret) {
        double score = 0;
        int p = 1;
        for (int i = 1; i < ret.size()-1; ++i) {
            score += this->pathcosts[p][ret[i]];
            p = ret[i];
        }
        score += this->pathcosts[p][1];
        return score;
    }
    inline double orderDiffDistScore(const int& a, const int& b, const vector<int>& ret, double score) {
        score -= this->pathcosts[ret[a-1]][ret[a]];
        score += this->pathcosts[ret[a-1]][ret[b]];
        score -= this->pathcosts[ret[b]][ret[b+1]];
        score += this->pathcosts[ret[a]][ret[b+1]];
        
        return score;
    }
    
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    MM();
    
    return 0;
}



Measured memory_bytes: 2124