#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace std;
using namespace __gnu_pbds;
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#else
#define dbg(...)
#endif
#define endl "\n"
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb(n) push_back(n)
#define F first
#define S second
#define mp(x, y) make_pair(x, y)
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define nop cout << -1 << endl;
#define ordered_set tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update>
const ll sup = 1e18;
const ll inf = -1e18;
const ll mod = 1e9 + 7;
const int N_Max = 2e5 + 7;
const int Nax = 15;
const int LOG = 18;
const int BITS = 30;
const int ALPHA = 26;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a;}
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);}
ll inv(ll N) {if (N == 1) return 1; return (mod - ((mod / N) * inv(mod % N)) % mod) % mod;}
vector<pair<int, int>> adj[N_Max];
ll dist[N_Max];
int N, M;
void dijkstra(int src){
set<pair<ll, int>> s;
for (int i = 1; i <= N; i++) dist[i] = 1e18;
dist[src] = 0;
s.insert({dist[src], src});
while (!s.empty()){
auto [d, Node] = *s.begin();
s.erase(s.begin());
if (dist[Node] < d) continue;
for (auto [child, w] : adj[Node]){
ll cost = d + w;
if (cost < dist[child]){
dist[child] = cost;
s.insert({dist[child], child});
}
}
}
}
void solve(){
}
int main(){
FAST
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int tc = 1;
// cin >> tc;
while (tc--) solve();
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNpbmNsdWRlIDxleHQvcGJfZHMvYXNzb2NfY29udGFpbmVyLmhwcD4gLy8gQ29tbW9uIGZpbGUKI2luY2x1ZGUgPGV4dC9wYl9kcy90cmVlX3BvbGljeS5ocHA+IC8vIEluY2x1ZGluZyB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGUKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7CiNpZm5kZWYgT05MSU5FX0pVREdFCiNpbmNsdWRlICJkZWJ1Zy5jcHAiCiNlbHNlCiNkZWZpbmUgZGJnKC4uLikKI2VuZGlmCiNkZWZpbmUgZW5kbCAiXG4iCiNkZWZpbmUgRkFTVCBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsgY2luLnRpZShOVUxMKTsKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBwYihuKSBwdXNoX2JhY2sobikKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBtcCh4LCB5KSBtYWtlX3BhaXIoeCwgeSkKI2RlZmluZSB5ZXMgY291dCA8PCAiWUVTIiA8PCBlbmRsOwojZGVmaW5lIG5vIGNvdXQgPDwgIk5PIiA8PCBlbmRsOwojZGVmaW5lIG5vcCBjb3V0IDw8IC0xIDw8IGVuZGw7CiNkZWZpbmUgb3JkZXJlZF9zZXQgdHJlZTxwYWlyPGludCwgaW50PiwgbnVsbF90eXBlLCBsZXNzPHBhaXI8aW50LCBpbnQ+PiwgcmJfdHJlZV90YWcsIHRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT4KY29uc3QgbGwgc3VwID0gMWUxODsKY29uc3QgbGwgaW5mID0gLTFlMTg7CmNvbnN0IGxsIG1vZCA9IDFlOSArIDc7CmNvbnN0IGludCBOX01heCA9IDJlNSArIDc7CmNvbnN0IGludCBOYXggPSAxNTsKY29uc3QgaW50IExPRyA9IDE4Owpjb25zdCBpbnQgQklUUyA9IDMwOwpjb25zdCBpbnQgQUxQSEEgPSAyNjsKbGwgZ2NkKGxsIGEgLCBsbCBiKSB7cmV0dXJuIGIgPyBnY2QoYiAsIGEgJSBiKSA6IGE7fQpsbCBsY20obGwgYSAsIGxsIGIpIHtyZXR1cm4gKGEgKiBiKSAvIGdjZChhICwgYik7fQpsbCBpbnYobGwgTikge2lmIChOID09IDEpIHJldHVybiAxOyByZXR1cm4gKG1vZCAtICgobW9kIC8gTikgKiBpbnYobW9kICUgTikpICUgbW9kKSAlIG1vZDt9Cgp2ZWN0b3I8cGFpcjxpbnQsIGludD4+IGFkaltOX01heF07CmxsIGRpc3RbTl9NYXhdOwppbnQgTiwgTTsKCnZvaWQgZGlqa3N0cmEoaW50IHNyYyl7CiAgICBzZXQ8cGFpcjxsbCwgaW50Pj4gczsKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IE47IGkrKykgZGlzdFtpXSA9IDFlMTg7CiAgICBkaXN0W3NyY10gPSAwOwogICAgcy5pbnNlcnQoe2Rpc3Rbc3JjXSwgc3JjfSk7CiAgICB3aGlsZSAoIXMuZW1wdHkoKSl7CiAgICAgICAgYXV0byBbZCwgTm9kZV0gPSAqcy5iZWdpbigpOwogICAgICAgIHMuZXJhc2Uocy5iZWdpbigpKTsKICAgICAgICBpZiAoZGlzdFtOb2RlXSA8IGQpIGNvbnRpbnVlOwogICAgICAgIGZvciAoYXV0byBbY2hpbGQsIHddIDogYWRqW05vZGVdKXsKICAgICAgICAgICAgbGwgY29zdCA9IGQgKyB3OwogICAgICAgICAgICBpZiAoY29zdCA8IGRpc3RbY2hpbGRdKXsKICAgICAgICAgICAgICAgIGRpc3RbY2hpbGRdID0gY29zdDsKICAgICAgICAgICAgICAgIHMuaW5zZXJ0KHtkaXN0W2NoaWxkXSwgY2hpbGR9KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KfQoKdm9pZCBzb2x2ZSgpewoJCn0KCmludCBtYWluKCl7CiAgICBGQVNUCiAgICAjaWZuZGVmIE9OTElORV9KVURHRQogICAgZnJlb3BlbigiaW5wdXQudHh0IiwiciIsc3RkaW4pOwogICAgZnJlb3Blbigib3V0cHV0LnR4dCIsInciLHN0ZG91dCk7CiAgICAjZW5kaWYKICAgIGludCB0YyA9IDE7CiAgICAvLyBjaW4gPj4gdGM7CiAgICB3aGlsZSAodGMtLSkgc29sdmUoKTsKICAgIHJldHVybiAwOwp9