#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
using namespace std;

const int MAX_N = 2001;
const int START_DISTANCE = 2000000000;
const int CITY_BITS = 11; // 1..2000
// const int DISTANCE_BITS = 30; //1..2k*500k = 1..1e9
const int DISTANCE_BITS = 9; //1..500

// #define MODE_DEBUG
// #define FULL_MESSAGE

#ifdef MODE_DEBUG
#define DEBUG(x) x
#else
#define DEBUG(x)
#endif

#define REP(x,n) for(int x=0;x<(n);++x)
#define VAR(x,n) decltype(n) x = (n)
#define FOREACH(x,c) for(VAR(x, (c).begin()); x != (c).end(); ++x)
#define CONTAINS(x,elem) ((x).find(elem) != (x).end())

struct Vertex {
    int parentIndex = -1;
    vector<pair<int,int>> edges;
    int distance = START_DISTANCE;
} graph[MAX_N];

auto dist_fn = [](const Vertex* a, const Vertex* b) {
    return a->distance == b->distance ? a<b : a->distance < b->distance;
};

std::set<Vertex*, decltype(dist_fn)> process_queue(dist_fn);


void inline writeBits(int value, int bits) {
    #ifdef MODE_DEBUG
        cout << "+ " << value << "\n";
    #else
        for(int mask = (1 << (bits-1)); mask; mask >>= 1) {
            cout << (value&mask ? "+ 1\n" : "+ 0\n");
        }
    #endif
    cout.flush();
}
int inline readBits(int bits) {
    int result = 0;
    #ifdef MODE_DEBUG
        cout << "?\n";
        cout.flush();
        cin >> result;
        return result;
    #else
        short bit;
        REP(x,bits)
            cout << "?\n";
        cout.flush();
        REP(x,bits) {
            cin >> bit;
            result = (result << 1) | bit;
        }
    #endif
    return result;
}

//city 1..2000 -> 11 bits
void inline writeCity(int city) {
    writeBits(city, CITY_BITS);
}
int inline readCity() {
    return readBits(CITY_BITS);
}

//distance 1..500 - 9 bits
//total distance 1..1e9 - 30 bits
void writeDistance(int distance) {
    writeBits(distance, DISTANCE_BITS);
}
int readDistance() {
    return readBits(DISTANCE_BITS);
}

void writeFlag(bool flag) {
    writeBits(flag, 1);
}
bool readFlag() {
    return readBits(1);
}

void writeSolution(int n) {
    cout << "!";
    REP(x,n) {
        cout << " " << graph[x+1].distance;
    }
    cout.flush();
}

void processEdge(int parentIndex, int childIndex, int weight) {
    Vertex& parent = graph[parentIndex];
    Vertex& child = graph[childIndex];
    DEBUG(cout << "  processing edge " << parentIndex << "->" << childIndex << ": " << child.distance << " >? " << parent.distance << " + " << weight << endl;)
    if (child.distance > parent.distance + weight) {
        if (child.distance != START_DISTANCE) {
            process_queue.erase(&child);
        }
        child.distance = parent.distance + weight;
        child.parentIndex = parentIndex;
        process_queue.insert(&child);
        DEBUG(cout << "  add " << childIndex << " to queue with distance " << child.distance << endl;)
    }
}

void process(int vIndex) {
    Vertex& root = graph[vIndex];
    DEBUG(cout << "  processing city " << vIndex << endl;)
    FOREACH(it, root.edges) {
        processEdge(vIndex, it->first, it->second);
    }
    DEBUG(cout << "  finished processing city " << vIndex << endl;)
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    string mode;
    int n,m,u,v,c;
    cin>>mode>>n>>m;
    REP(x,m) {
        cin>>u>>v>>c;
        graph[u].edges.push_back({v,c});
        graph[v].edges.push_back({u,c});
    }
    graph[1].distance = 0;
    process(1);

    if (mode == "Algosia") {
        int previousCity = 1;
        REP(x,n-1) {
            //sugestia Bajtka
            int cityTo = readCity();
            int weight = -1;
            if (cityTo != 0) {
                int cityFrom = readCity();
                weight = readDistance();
                DEBUG(cout<<" Suggested direction is "<<cityFrom<<"->"<<cityTo<<" with distance "<<weight<<endl;)
                processEdge(cityFrom, cityTo, weight);
            }
            DEBUG(
                cout << " queue size is " << process_queue.size() << "[ ";
                FOREACH(elem, process_queue) {
                    cout << "(" << (*elem-graph) << "/" << (*elem)->distance << ") ";
                }
                cout << "]" << endl;
            )
            if (!process_queue.empty()) {
                Vertex* closest = *process_queue.begin();
                process_queue.erase(process_queue.begin());
                int closestIndex = closest-graph;
                DEBUG(cout << " closest is " << closestIndex << " with distance " << closest->distance << endl;)
                process(closestIndex);

                if (x != n-2) {
                    int closestWeight = closest->distance - graph[closest->parentIndex].distance;
                    #ifdef FULL_MESSAGE
                        writeCity(closestIndex);
                        writeCity(closest->parentIndex);
                        writeDistance(closestWeight);
                    #else
                        if (closestIndex == cityTo && closestWeight == weight) {
                            writeCity(closestIndex);
                            writeFlag(false);
                        } else {
                            writeCity(closestIndex);
                            if (closestIndex == cityTo) {
                                writeFlag(true);
                            }
                            writeCity(closest->parentIndex);
                            writeDistance(closestWeight);
                        }
                    #endif
                }
                process(closestIndex);
            }
        }
        writeSolution(n);
    } else {
        int previousCity;
        REP(x,n-1) {
            int cityTo;
            if (x) {
                cityTo = readCity();
                process_queue.erase(&graph[cityTo]);
                bool readMore = true;
                #ifndef FULL_MESSAGE
                    if (cityTo == previousCity) {
                        readMore = readFlag();
                    }
                #endif
                if (readMore) {
                    int cityFrom = readCity();
                    int distance = readDistance();
                    graph[cityTo].distance = graph[cityFrom].distance + distance;
                    graph[cityTo].parentIndex = cityFrom;
                }
                DEBUG(cout << " before process" << endl;)
                process(cityTo);
                DEBUG(cout << " after process;";)
            }
            DEBUG(
                cout << " queue size is " << process_queue.size() << "[ ";
                FOREACH(elem, process_queue) {
                    cout << "(" << (*elem-graph) << "/" << (*elem)->distance << ") ";
                }
                cout << "]" << endl;
            )

            if (process_queue.empty()) {
                writeCity(0);
                previousCity = 0;
            } else {
                Vertex* closest = *process_queue.begin();
                process_queue.erase(process_queue.begin());
                int closestIndex = closest-graph;
                DEBUG(cout << " closest is " << closestIndex << " with distance " << closest->distance << endl;)
                
                writeCity(closestIndex);
                writeCity(closest->parentIndex);
                writeDistance(closest->distance - graph[closest->parentIndex].distance);

                previousCity = closestIndex;
            }
        }
    }
}