// library begin: "lib/template.hpp" //https://github.com/ryoku1020/lib #ifdef TEMPLATE #else #define TEMPLATE #pragma GCC optimize("O3") #include #include using namespace std; namespace ryoku{} using uint=unsigned; using ll=long long; using ull=unsigned long long; using ld=long double; using pii=pair; using pll=pair; using i128=__int128; using u128=unsigned __int128; templateusing vc=vector; templateusing vvc=vc>; templateusing vvvc=vvc>; templateusing smpq=priority_queue,greater>; templateusing bipq=priority_queue; using vi=vc; using vvi=vvc; using vl=vc; using vvl=vvc; #define rep(i,n) for(ll i=0;i<(ll)(n);i++) #define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++) #define DREP(i,n,m) for(ll i=ll(n);i>=ll(m);i--) #define drep(i,n) for(ll i=(ll(n)-1);i>=0;i--) #define rall(x) x.rbegin(),x.rend() #define mp(...) make_pair(__VA_ARGS__) #define pb push_back #define fi first #define se second #define is insert #define bg begin() #define ed end() #define all(x) x.begin(),x.end() istream& operator>>(istream&is,i128&x){ string s;if(!(is>>s))return is; u128 y=0; int i=0,neg=0; if(s[0]=='-'||s[0]=='+')neg=s[0]=='-',i=1; for(;i<(int)s.size();i++)y=y*10+s[i]-'0'; x=neg?(y?-(i128)(y-1)-1:0):(i128)y; return is; } ostream& operator<<(ostream&os,i128 x){ if(x==0)return os<<0; if(x<0)os<<"-"; u128 y=x<0?-(u128)x:(u128)x; string s; while(y)s.pb('0'+y%10),y/=10; reverse(all(s)); return os<>a;} void scan(ll&a){cin>>a;} void scan(i128&a){cin>>a;} void scan(string&a){cin>>a;} void scan(char&a){cin>>a;} void scan(uint&a){cin>>a;} void scan(ull&a){cin>>a;} void scan(bool&a){cin>>a;} void scan(ld&a){ cin>>a;} template void scan(pair&p){ scan(p.first); scan(p.second); } templatevoid scan(C&a){for(auto&x:a)scan(x);} void read(){} templatevoid read(Head&head,Tail&... tail){scan(head); read(tail...);} #define INT(...) int __VA_ARGS__; read(__VA_ARGS__); #define LL(...) ll __VA_ARGS__; read(__VA_ARGS__); #define ULL(...) ull __VA_ARGS__; read(__VA_ARGS__); #define STR(...) string __VA_ARGS__; read(__VA_ARGS__); #define VC(type,name,...) vector name(__VA_ARGS__); read(name); #define VVC(type,name,size,...) vector> name(size,vector(__VA_ARGS__)); read(name); templatevoid print(T a){cout<void print(vectora){for(int i=0;i<(int)a.size();i++){if(i)cout<<" ";print(a[i]);}} void PRT(){cout<void PRT(T a){print(a); cout<void PRT(Head head,Tail... tail){print(head); cout<<" "; PRT(tail...); return;} templateint chmin(T&x,F y){return x>y?(x=y,1):0;} templateint chmax(T&x,F y){return xT floor(T a,T b){return a/b-(a%b&&((a<0)!=(b<0)));} templateT ceil(T a,T b){return a/b+(a%b&&((a<0)==(b<0)));} templateT bmod(T x,T y){return x-y*floor(x,y);} template pairdivmod(T x,T y){ T q=floor(x,y); return{q,x-q*y}; } void YesNo(bool b){cout<<(b?"Yes":"No")<stovi(const string&s,const string&S){ vcv(s.size()); rep(i,s.size()){ auto t=S.find(s[i]); assert(t!=string::npos); v[i]=t; } return v; } template T isqrt(T x){ T F=sqrtl(x); if(F*F>x)F--; return F; } templateC sorted(C a){ sort(all(a)); return a; } templateC reved(C a){ reverse(all(a)); return a; } template pair,vc>compress(const vc&a){ vcxs=a; sort(all(xs)); xs.erase(unique(all(xs)),xs.end()); vcb(a.size()); rep(i,a.size())b[i]=lower_bound(all(xs),a[i])-xs.begin(); return{b,xs}; } template auto make_vec(int n,T x){ return vc(n,x); } template auto make_vec(int n,Args...args){ return vc(n,make_vec(args...)); } templateT tri(T x){return x*(x-1)/2;} //[l,r) templateT tri(T l,T r){return (r-l)*(l+r-1)/2;} //n を先頭に持ってくる template C rot(C v,int n){ rotate(v.begin(),v.begin()+n,v.end()); return v; } template C concat(C a,const C&b){ a.insert(a.end(),b.begin(),b.end()); return a; } template auto rle(const Container&cv){ using T=typename Container::value_type; vc>res; for(const auto&x:cv){ if(res.empty()||res.back().fi!=x)res.pb({x,1}); else res.back().se++; } return res; } template vciota(int n){ vcv(n);rep(i,n)v[i]=i; return v; } template vcargsort(const C&a){ auto idx=iota(a.size()); sort(all(idx),[&](int i,int j){ return (minfirst?make_pair(a[i],i)make_pair(a[j],j)); }); return idx; } template auto trans(const C&a){ using T=typename C::value_type::value_type; assert(a.size()&&a[0].size()); rep(i,a.size())assert(a[i].size()==a[0].size()); vvcb(a[0].size(),vc(a.size())); rep(i,a.size())rep(j,a[0].size())b[j][i]=a[i][j]; return b; } vctrans(const vc&a){ assert(a.size()&&a[0].size()); rep(i,a.size())assert(a[i].size()==a[0].size()); vcb(a[0].size(),string(a.size(),0)); rep(i,a.size())rep(j,a[0].size())b[j][i]=a[i][j]; return b; } templatell sz(const C&a){return (int)a.size();} templateauto lb(const C&a,const T&x){return lower_bound(all(a),x);} templateauto ub(const C&a,const T&x){return upper_bound(all(a),x);} templateint popcount(T n){return __builtin_popcountll(n);} templateL sum(const C&a){return accumulate(all(a),L(0));} template struct subset_view{ T s; struct iterator{ T s,x; bool done; T operator*()const{return x;} iterator&operator++(){ if(x==0)done=true; else x=(x-1)&s; return*this; } bool operator!=(const iterator&r)const{return done!=r.done;} }; iterator begin()const{return{s,s,false};} iterator end()const{return{s,0,true};} }; template subset_viewsubset(T s){return{s};} templateauto max(const C&a){return *max_element(all(a));} templateauto min(const C&a){return *min_element(all(a));} templatell argmin(const C&a){return min_element(all(a))-a.begin();} templatell argmax(const C&a){return max_element(all(a))-a.begin();} template vcpresum(const C&a){ vcret(a.size()+1); rep(i,a.size())ret[i+1]=ret[i]+a[i]; return ret; } template vc&operator+=(vc&a,F b){ for(auto&v:a)v+=b; return a; } template vc&operator-=(vc&a,F b){ for(auto&v:a)v-=b; return a; } template vc&operator*=(vc&a,F b){ for(auto&v:a)v*=b; return a; } template array&operator+=(array&a,F b){ for(auto&v:a)v+=b; return a; } template array&operator-=(array&a,F b){ for(auto&v:a)v-=b; return a; } template array&operator*=(array&a,F b){ for(auto&v:a)v*=b; return a; } template constexpr T pow(T a,T b){ T res=1; while(b){ if(b&1)res*=a; a*=a; b/=2; } return res; } template struct temporary{ T& x;T old; templatetemporary(T&x,U&&y):x(x),old(x){ x=std::forward(y); } ~temporary(){x=std::move(old);} temporary(const temporary&)=delete; }; template temporary(T&,U&&)->temporary; #define CAT_(a,b) a##b #define CAT(a,b) CAT_(a,b) #define WITH(x,y) temporary CAT(_tmp_,__COUNTER__)(x,y) constexpr ll two(ll a){return (1ll<(10,a);} templateconstexpr T inf=numeric_limits::max()/2-1; template<>constexpr pll inf ={inf,inf}; templateconstexpr T neg_inf=-inf; template<>constexpr pll neg_inf ={-inf,-inf}; templateC UNIQUE(C&a){ sort(all(a)); a.erase(unique(all(a)),a.end()); return a; } template int tbit(T x){ using U=make_unsigned_t; U y=(U)x; if(!y)return -1; if(sizeof(U)>sizeof(ull)&&(u128)y>>64)return 127-__builtin_clzll((ull)((u128)y>>64)); return 63-__builtin_clzll((ull)y); } template int lbit(T x){ using U=make_unsigned_t; U y=(U)x; if(!y)return -1; if((ull)y)return __builtin_ctzll((ull)y); return 64+__builtin_ctzll((ull)((u128)y>>64)); } template int tbit(T x,int p){ using U=make_unsigned_t; constexpr int W=numeric_limits::digits; U y=(U)x; if(p<0)return -1; if(p>=W-1)return tbit(y); return tbit(y&((U(1)<<(p+1))-1)); } template int lbit(T x,int p){ using U=make_unsigned_t; constexpr int W=numeric_limits::digits; U y=(U)x; if(p<0)return lbit(y); if(p>=W)return -1; return lbit(y&(~U(0)< void dbg(const Ts&...xs){} #define dbg(...) ((void)0) #define mark(...) ((void)0) #endif struct template_setup{ template_setup(){ #if defined(LOCAL)&&!defined(INTERACTIVE)&&!defined(SAMPLE_TEST) freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif cin.tie(0)->sync_with_stdio(0); #ifdef LOCAL cout< struct edge{ int from,to,id; [[no_unique_address]]T cost; #ifdef LOCAL friend ostream&operator<<(ostream&os,const edge&e){ return os<<"{from:"< struct static_graph{ constexpr static bool directed(){return is_directed;} using edge=::ryoku::edge; using cost_t=T; private: int n; mutable bool built=false,inv_built=false; vcedges; mutable vcstart,inv_start; mutable vccsr,inv_csr; public: static_graph(int n):n(n),start(n+1),inv_start(n+1){assert(n>=0);} static_graph(int n,int m):static_graph(n){assert(m>=0);edges.reserve(m);} void resize(int size){ assert(n<=size&&!built); assert(!inv_built); n=size; start.resize(n+1); inv_start.resize(n+1); } void add_edge(const edge&e){ assert(!built&&!inv_built); assert(0<=e.from&&e.from void input(int m){ assert(m>=0); rep(i,m){ INT(a,b); a-=substract;b-=substract; add_edge(a,b); } build(); } void build()const{ if(built)return; built=true; start.assign(n+1,0); for(auto&e:edges){ ++start[e.from]; if constexpr(!is_directed)++start[e.to]; } rep(i,n)start[i+1]+=start[i]; csr.resize(start[n]); for(auto it=edges.rbegin();it!=edges.rend();++it){ auto&e=*it; csr[--start[e.from]]=e; if constexpr(!is_directed)csr[--start[e.to]]={e.to,e.from,e.id,e.cost}; } } void buildinv()const{ if(inv_built)return; inv_start.assign(n+1,0); for(auto&e:edges){ ++inv_start[e.to]; if constexpr(!is_directed)++inv_start[e.from]; } rep(i,n)inv_start[i+1]+=inv_start[i]; inv_csr.resize(inv_start[n]); for(auto it=edges.rbegin();it!=edges.rend();++it){ auto&e=*it; inv_csr[--inv_start[e.to]]={e.to,e.from,e.id,e.cost}; if constexpr(!is_directed)inv_csr[--inv_start[e.from]]={e.from,e.to,e.id,e.cost}; } inv_built=true; } auto operator[](int u){ build(); assert(0<=u&&u(csr.data()+start[u],start[u+1]-start[u]); } auto operator[](int u)const{ build(); assert(0<=u&&u(csr.data()+start[u],start[u+1]-start[u]); } auto inv(int u){ buildinv(); assert(0<=u&&u(inv_csr.data()+inv_start[u],inv_start[u+1]-inv_start[u]); } auto inv(int u)const{ buildinv(); assert(0<=u&&u(inv_csr.data()+inv_start[u],inv_start[u+1]-inv_start[u]); } const vc&all_edges()const{return edges;} int edge_size()const{return edges.size();} edge get_edge(int id)const{ assert(0<=id&&id vvcadj()const{ vvcres(n,vc(n)); for(auto&e:edges){ res[e.from][e.to]=e.cost; if constexpr(!is_directed)res[e.to][e.from]=e.cost; } return res; } void clear(){ built=false; inv_built=false; edges.clear(); csr.clear(); inv_csr.clear(); start.assign(n+1,0); inv_start.assign(n+1,0); } template void sort(int i,F f){ build(); assert(0<=i&&ig(n); rep(i,m){ LL(u,v,w);--u,--v; if(i+1<62&&(i128(1)<<(i+1))*w<=2e18){ g.add_edge(u,v,w<<(i+1)); } } while(q--){ LL(a,b);--a,--b; auto A=[&](ll a){ unordered_mapmd; smpqque; auto push=[&](ll x,ll y){ if(!md.count(x)||md[x]>y){ md[x]=y;que.push({y,x}); } }; push(a,0); while(que.size()){ auto[d,v]=que.top();que.pop(); if(md[v]!=d)continue; for(auto&e:g[v]){ push(e.to,e.cost+d); } }return md; }; auto mda=A(a); auto mdb=A(b); ll ans=4e18; ll mdbmin=2e18; for(auto&[x,y]:mdb)chmin(mdbmin,s[x]+y); for(auto&[x,y]:mda){ chmin(ans,mdbmin+s[x]+y); if(x==b)chmin(ans,y); else{ chmin(ans,y+s[x]+s[b]); } } PRT(ans); } } signed main(){ int t=1; // cin >> t; while(t--)solve(); }