#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58001;
    constexpr int inf = 1e9 + 7;

    int N, A, Q = 0, S = 0, usedCnt = 0, T = 0;
    bool last = true;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];

    void upd(int v) {
        for (auto [to, w]: adj[v]) {
            if (!used[to] && dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                st.emplace(dist[to] = dist[v] + w, to);
            }
        }
    }
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    ::N = N, ::A = A;

    fill(dist, dist + N, inf);
    dist[0] = 0;
    used[0] = true;


    for (int i = 0; i < A; ++i) {
        adj[U[i]].emplace_back(V[i], C[i]);
        adj[V[i]].emplace_back(U[i], C[i]);
    }

    upd(0);

    SendA(1);
    for (int i = 0; i < 20; ++i) {
        SendA(0);
    }
}

void ReceiveA(bool x) {
    b[Q++] = x;
    T += last;

    if (last && b[Q - 1] == 0 || !last && (Q - T) % 20 == 0) {
        int v = -228, d = -228;

        if (!last) {
            v = 0, d = 0;
            int s = Q - 20;

            for (int i = 0; i < 11; ++i) {
                v |= b[s + i] << i;
            }
            for (int i = 0; i < 9; ++i) {
                d |= b[s + 11 + i] << i;
            }

            if (v != 0) {
                st.erase({dist[v], v});
                st.emplace(dist[v] = min(dist[v], S + d), v);
                upd(v);
            }
        }

        last = true;

        if (st.empty()) {
            return;
        }

        auto [dis, to] = *st.begin();
        st.erase(st.begin());
        assert(!used[to]);
        used[to] = true;

        upd(to);

        int diff = dis - S;
        S = dis;

        if (to == v && dis == d) {
            SendA(0);
        } else {
            SendA(1);
            for (int i = 0; i < 11; ++i) {
                SendA(to >> i & 1);
            }
            for (int i = 0; i < 9; ++i) {
                SendA(diff >> i & 1);
            }
        }
    } else {
        last = false;
    }
}

std::vector<int> Answer() {
    std::vector<int> ans(N);
    for (int k = 0; k < N; ++k) {
        ans[k] = dist[k];
    }
    return ans;
}

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

namespace {
    constexpr int maxN = 2000, maxQ = 58000;
    constexpr int inf = 1e9 + 7;

    int N, B, Q = 0, S = 0, Sh = 0, T = 0;
    bool last = true;

    vector<pair<int, int>> adj[maxN];
    set<pair<int, int>> st;

    int dist[maxN];
    bool used[maxN], b[maxQ];

    void upd(int v) {
        for (auto [to, w]: adj[v]) {
            if (!used[to] && dist[to] > dist[v] + w) {
                st.erase({dist[to], to});
                st.emplace(dist[to] = dist[v] + w, to);
            }
        }
    }
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    ::N = N, ::B = B;

    fill(dist, dist + N, inf);

    for (int i = 0; i < B; ++i) {
        adj[S[i]].emplace_back(T[i], D[i]);
        adj[T[i]].emplace_back(S[i], D[i]);
    }
}

void ReceiveB(bool y) {
    b[Q++] = y;

    T += last;

    if (last && b[Q - 1] == 0 || !last && (Q - T) % 20 == 0) {
        if (!last) {
            int v = 0, d = 0, s = Q - 20;

            for (int i = 0; i < 11; ++i) {
                v |= b[s + i] << i;
            }
            for (int i = 0; i < 9; ++i) {
                d |= b[s + 11 + i] << i;
            }

            S += d;
            used[v] = true;
            st.erase({dist[v], v});
            dist[v] = S;

//            cerr << "B received: " << v << "; dist0 = " << S << "; diff = " << d << endl;

            upd(v);
        } else {
            S = Sh;
        }

        last = true;

        if (st.empty()) {
            SendB(0);
        } else {
            auto [dis, to] = *st.begin();
//            st.erase(st.begin());
            assert(dis >= S);
            assert(!used[to] && dis >= S);
            Sh = dis;
            upd(to);

            SendB(1);
            for (int i = 0; i < 11; ++i) {
                SendB(to >> i & 1);
            }
            for (int i = 0; i < 9; ++i) {
                SendB((dis - S) >> i & 1);
            }
        }
    } else {
        last = false;
    }
}