#include #include using namespace std; using namespace atcoder; #define rep(i, n) for (long long i = 0; i < (long long)(n); i++) #define repn(i,end) for(long long i = 0; i <= (long long)(end); i++) #define reps(i,start,end) for(long long i = start; i < (long long)(end); i++) #define repsn(i,start,end) for(long long i = start; i <= (long long)(end); i++) #define ll long long #define ld long double #define all(a) (a).begin(),(a).end() // << std::fixed << std::setprecision(10) const ll INF = 1LL << 60; template bool chmin(T& a, T b){ if(a > b){ a = b; return true; } return false; } template bool chmax(T& a, T b){ if(a < b){ a = b; return true; } return false; } //grid探索用 vector _tate = {0,-1,0,1,1,-1,-1,1}; vector _yoko = {1,0,-1,0,1,1,-1,-1}; ll lpow(ll x,ll n){ ll ans = 1; while(n >0){ if(n & 1)ans *= x; x *= x; n >>= 1; } return ans; } int main(){ ll n,m;cin >> n >> m; vector>> g(n);//頂点,距離 rep(i,m){ ll u,v,w;cin >> u >> v >> w; u--;v--; g[u].insert({v,w}); } ll K;cin >> K; set> abc; rep(z,K){ ll a,b,c;cin >> a >> b >> c; a--;b--;c--; abc.insert({a,b,c}); } vector>> in(n);//距離,頂点(from) vector dis(n,INF); dis[0] = 0; for(auto &p:g[0]){ in[p.first].insert({dis[0] + p.second,0}); } //0は別でやる reps(i,1,n){ for(auto &p:in[i]){ vector> used; auto [cost,from] = p; chmin(dis[i],cost); for(auto &q: g[i]){ auto [to,w] = q; if(abc.count({from,i,to}))continue; in[to].insert({cost + w,i}); used.push_back({to,w}); } for(auto &pr:used){ g[i].erase(pr); } } } if(dis[n-1] == INF){ cout << -1 << endl; }else{ cout << dis[n-1] << endl; } }