#include using namespace std; typedef long long ll; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b #define vl vector #define vii vector> #define vll vector> #define vvi vector> #define vvl vector> #define vvii vector>> #define vvll vector>> #define vst vector #define pii pair #define pll pair #define pb push_back #define all(x) (x).begin(),(x).end() #define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end()) #define fi first #define se second #define mp make_pair #define si(x) int(x.size()) const int mod=998244353,MAX=300005; const ll INF=15LL<<58; struct UF{ int n; vector par,size,edge; void init(int n_){ n=n_; par.assign(n,-1); size.assign(n,1); edge.assign(n,0); for(int i=0;i>N>>M>>Q; vl S(N); for(int i=0;i>S[i]; } UF uf;uf.init(N); vector> E; for(ll i=1;i<=M;i++){ ll u,v,w;cin>>u>>v>>w;u--;v--; if(w==0){ uf.unite(u,v); }else{ for(ll q=0;q2000000000000000000LL) break; } if(w<=2000000000000000000LL){ E.pb({u,v,w}); } //cout< MA; for(int i=0;i,greater> PQ; dis[i]=0; PQ.push(mp(0,i)); vi miru; while(!PQ.empty()){ auto [d,u]=PQ.top();PQ.pop(); if(dis[u]>a>>b;a--;b--; a=uf.root(a); b=uf.root(b); ll ans=INF; chmin(ans,MI[a]+MI[b]); //cout<