#ifndef ONLINE_JUDGE #define _GLIBCXX_DEBUG #endif #include #include using namespace std; using ll=long long; using ld=long double; using st=string; using P=pair; typedef atcoder::modint mint; ll inf=4e18; template auto vec(const ll (&sizes)[s], const T& init = T()){ if constexpr(i < s) return vector(sizes[i], vec(sizes, init)); else return init; } struct Edge{ll to,cost=1;}; bool operator>(Edge a,Edge b){ return a.cost>b.cost; } void dijkstra(vector> &graph,ll s,vector &dis){ priority_queue,greater> q; dis=vector(graph.size(),inf); q.push({s,0}); dis[s]=0; while(!q.empty()){ ll f=q.top().to,c=q.top().cost; q.pop(); if(dis[f]>n>>m>>q; auto s=vec({n},0); auto g=vec({n+1,0},{0,0}); auto g2=vec({128,0},{0,0}); map ma; for(ll i=0;i>s[i]; g[n].push_back({i,s[i]}); g[i].push_back({n,s[i]}); } for(ll i=1;i<=m;i++){ cin>>u>>v>>w; if(i<=62&&w>>(62-i)==0){ w<<=i; }else{ continue; } --u,--v; g[u].push_back({v,(ll)w}); g[v].push_back({u,(ll)w}); if(!ma.contains(u)) ma[u]=i*2; if(!ma.contains(v)) ma[v]=i*2+1; g2[ma[u]].push_back({ma[v],(ll)w}); g2[ma[v]].push_back({ma[u],(ll)w}); } auto dis=vec({n+1},inf); auto dis2=vec({128},inf); dijkstra(g,n,dis); ll ans; for(ll i=0;i>u>>v; --u,--v; ans=dis[u]+dis[v]; // cout<