ICPC2021E_WA.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
using ll=long long;

long long powll(long long x,long long n){
  long long res=1;
  while(n>0){
    if(n&1){
      res*=x;
    }
    x*=x;
    n>>=1;
  }
  return res;
}

long long pow_mod(long long x,long long n,long long mod){
  long long res=1;
  while(n>0){
    if(n&1){
      res*=x;
      res%=mod;
    }
    x*=x;
    x%=mod;
    n>>=1;
  }
  return res;
}


const long long mod=1000000007;

typedef struct edge{
	ll to;
	ll cost;
  bool is_taxi;
}Edge;
typedef pair<int,pair<int,int>> P;

struct F{
  ll cost;
  ll to;
  ll cnt=0;
  bool is_ride=false;
};

struct Q{
  ll cost;
  ll cnt=0;
};

bool operator<(const F A,const F B){
  if(A.cnt>50 || B.cnt>50){
    return A.cnt<B.cnt;
  }
  ll A_wait=powll(2,A.cnt)-1;
  ll B_wait=powll(2,B.cnt)-1;
  return A.cost+A_wait<B.cost+B_wait;
}

bool operator>(const F A,const F B){
  return B<A;
}

F operator+(const F A,const long long B){
  return F{A.cost+B,A.to,A.cnt,A.is_ride};
}

long long INF=1000000000000000000;
int V;
vector<Edge> G[20000];
F d[20000][2];

void dijkstra(int s){
  priority_queue<F,vector<F>,greater<F>> que;
	for(int i=0;i<V;i++){
    d[i][0]=F{INF,-1,1000000000,false};
    d[i][1]=F{INF,-1,1000000000,false};
  }
	d[s][0]=F{0,-1,0,false};
	que.push(F{0,s,0,false});
	while(!que.empty()){
		F p=que.top();que.pop();
		int v=p.to;
    int cnt=p.cnt;
		if(true){
		  for(unsigned int i=0;i<G[v].size();i++){
		    Edge e=G[v][i];
        //cerr<<v<<"->"<<e.to<<" "<<d[v].cost<<" "<<e.cost<<" "<<d[v].to<<" "<<endl;
			  if(e.is_taxi){
          F tmp;
          if(p.is_ride){
            tmp=F{d[v][1].cost+e.cost,e.to,d[v][1].cnt,true};
          }else{
            tmp=F{d[v][0].cost+e.cost,e.to,d[v][0].cnt+1,true};
          }
          // if(d[v][0]<d[v][1]){
          //   tmp=F{d[v][0].cost+e.cost,e.to,d[v][0].cnt+1,true};
          // }else{
          //   tmp=F{d[v][1].cost+e.cost,e.to,d[v][1].cnt,true};
          // }
          if(tmp<d[e.to][1]){
            d[e.to][1]=tmp;
            que.push(tmp);
          }
          // if(tmp2<d[e.to][1]){
          //   d[e.to][1]=tmp2;
           // que.push(tmp2);
          //}
        }else{
          F tmp;
          if(p.is_ride){
            tmp=F{d[v][1].cost+e.cost,e.to,d[v][1].cnt,false};
          }else{
            tmp=F{d[v][0].cost+e.cost,e.to,d[v][0].cnt,false};
          }
        
          // if(d[v][0]<d[v][1]){
          //   tmp=F{d[v][0].cost+e.cost,e.to,d[v][0].cnt,false};          
          // }else{
          //   tmp=F{d[v][1].cost+e.cost,e.to,d[v][1].cnt,false};
          // }
          if(tmp<d[e.to][0]){
            d[e.to][0]=tmp;
            que.push(tmp);
           }
          // if(tmp2<d[e.to][0]){
          //   d[e.to][0]=tmp2;
          //   que.push(tmp2);
          // }
        }
      }
		}
	}
}

void solve(ll n,ll p,ll q){
  V=n;
  ll a,b,c;
  for(int i=0;i<p;i++){
    cin>>a>>b>>c;
    G[a-1].push_back(Edge{b-1,c,false});
    G[b-1].push_back(Edge{a-1,c,false});
  }
  for(int i=0;i<q;i++){
    cin>>a>>b>>c;
    G[a-1].push_back(Edge{b-1,c,true});
    G[b-1].push_back(Edge{a-1,c,true});
  }
  // for(int i=0;i<n;i++){
  //   cerr<<"i:"<<i+1<<endl;
  //   for(Edge j:G[i]){
  //     cerr<<j.to+1<<" ";
  //   }
  //   cerr<<endl<<endl;
  // }
  dijkstra(0);
  // for(int i=0;i<n;i++){
  //   cerr<<d[i].cost<<" "<<d[i].cnt<<" "<<d[i].cost+pow_mod(2,d[i].cnt,mod)-1<<endl;
  // }
  if(d[n-1][0].cost>=INF && d[n-1][1].cost>=INF){
    cout<<-1<<endl;
  }else{
    //cerr<<"pl:"<<pl<<" "<<d[n-1].cnt<<endl;
    if(d[n-1][0]<d[n-1][1]){
      cout<<(d[n-1][0].cost+pow_mod(2,d[n-1][0].cnt,mod)-1)%mod<<endl;
    }else{
      cout<<(d[n-1][1].cost+pow_mod(2,d[n-1][1].cnt,mod)-1)%mod<<endl;
    }
  }
  for(int i=0;i<n;i++){
    G[i].clear();
  }
  return;
}

int main(){
  ll n,p,q;
  while(true){
    cin>>n>>p>>q;
    if(n==0 && p==0 && q==0){
      break;
    }
    solve(n,p,q);
  }
  return 0;
}