#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "Azer.h"
const int INF = 1e9 + 69;
struct Edge{
int u, v, w;
Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
};
struct P{
int i, w;
P(int i = 0, int w = 0): i(i), w(w){}
};
struct compare{
bool operator () (P a, P b){return a.w > b.w;}
};
vector<int> gen_dis(int n, vector<Edge> e){
vector<vector<P>> graph(n);
for(auto i: e){
int u = i.u, v = i.v, w = i.w;
graph[u].push_back(P(v, w));
graph[v].push_back(P(u, w));
}
priority_queue<P, vector<P>, compare> pq;
vector<int> dis(n, INF);
for(int i = 0; i < n; ++i) if (dis[i] == INF){
dis[i] = 0; pq.push(P(i, 0));
while(pq.size()){
P u = pq.top(); pq.pop();
for(P v: graph[u.i]){
if (minimize(dis[v.i], dis[u.i] + v.w))
pq.push(P(v.i, dis[v.i]));
}
}
}
return dis;
}
void dfs(int u, vector<vector<int>> &graph, vector<int> &parent){
for(int v: graph[u]) if (parent[v] == -1){
parent[v] = u;
dfs(v, graph, parent);
}
}
int n1;
vector<Edge> e1;
vector<bool> infoA;
void InitA(int n, int m, vector<int> u, vector<int> v, vector<int> w){
n1 = n;
e1.clear(); infoA.clear();
for(int i = 0; i < m; ++i)
e1.push_back(Edge(u[i], v[i], w[i]));
vector<int> dih = gen_dis(n1, e1);
vector<vector<int>> graph(n1);
vector<int> parent(n1, -1);
for(Edge i: e1){
int u = i.u, v = i.v, w = i.w;
if (dih[u] == dih[v] + w) graph[v].push_back(u);
if (dih[v] == dih[u] + w) graph[u].push_back(v);
}
for(int i = 0; i < n1; ++i) if (dih[i] == 0 && parent[i] == -1){
parent[i] = i;
dfs(i, graph, parent);
}
vector<int> diff(n1);
for(int i = 0; i < n1; ++i) diff[i] = dih[i] - dih[parent[i]];
for(int i = 0; i < n1; ++i){
bitset<11> ver(parent[i]);
bitset<9> weight(diff[i]);
for(int j= 0; j < 11; ++j) SendA(ver[j]);
for(int j= 0; j < 9; ++j) SendA(weight[j]);
}
}
void ReceiveA(bool x){
infoA.push_back(x);
}
vector<int> Answer(){
vector<int> dih = gen_dis(n1, e1);
return dih;
}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MASK(i) (1ULL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
#define ALL(v) (v).begin(), (v).end()
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll gcd(ll a, ll b){return __gcd(a, b);}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}
ll LASTBIT(ll mask){return (mask) & (-mask);}
int pop_cnt(ull mask){return __builtin_popcountll(mask);}
int ctz(ull mask){return __builtin_ctzll(mask);}
int logOf(ull mask){return 63 - __builtin_clzll(mask);}
//mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b) {a = b; return true;}
return false;
}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b) {a = b; return true;}
return false;
}
template <class T>
void printArr(T container, string separator = " ", string finish = "\n", ostream &out = cout){
for(auto item: container) out << item << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
#include "Baijan.h"
const int INF = 1e9 + 69;
struct Edge{
int u, v, w;
Edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w){}
};
struct P{
int i, w;
P(int i = 0, int w = 0): i(i), w(w){}
};
struct compare{
bool operator () (P a, P b){return a.w > b.w;}
};
vector<int> gen_dis(int n, vector<Edge> e){
vector<vector<P>> graph(n);
for(auto i: e){
int u = i.u, v = i.v, w = i.w;
graph[u].push_back(P(v, w));
graph[v].push_back(P(u, w));
}
priority_queue<P, vector<P>, compare> pq;
vector<int> dis(n, INF);
for(int i = 0; i < n; ++i) if (dis[i] == INF){
dis[i] = 0; pq.push(P(i, 0));
while(pq.size()){
P u = pq.top(); pq.pop();
for(P v: graph[u.i]){
if (minimize(dis[v.i], dis[u.i] + v.w))
pq.push(P(v.i, dis[v.i]));
}
}
}
return dis;
}
void dfs(int u, vector<vector<int>> &graph, vector<int> &parent){
for(int v: graph[u]) if (parent[v] == -1){
parent[v] = u;
dfs(v, graph, parent);
}
}
int n2;
vector<Edge> e2;
vector<bool> infoB;
void InitB(int n, int m, vector<int> u, vector<int> v, vector<int> w){
e2.clear(); infoB.clear();
n2 = n;
for(int i = 0; i < m; ++i)
e2.push_back(Edge(u[i], v[i], w[i]));
}
void ReceiveB(bool x){
infoB.push_back(x);
if (infoB.size() == n2 * 20){
vector<int> dih = gen_dis(n2, e2);
vector<vector<int>> graph(n2);
vector<int> parent(n2, -1);
for(Edge i: e2){
int u = i.u, v = i.v, w = i.w;
if (dih[u] == dih[v] + w) graph[v].push_back(u);
if (dih[v] == dih[u] + w) graph[u].push_back(v);
}
for(int i = 0; i < n2; ++i) if (dih[i] == 0 && parent[i] == -1){
parent[i] = i;
dfs(i, graph, parent);
}
}
}
