#include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 1 << 21;struct Edge {    int v, d;    Edge *next;    Edge (int v, int d, Edge *next) : v(v), d(d), next(next) {}    Edge () {}}*head[101];int n, m, cnt, e, K, tp[N], F[N], dis[N];void dfs(int u, int p) {    if( u == m) {        if( !F[p]) tp[++ cnt] = p; F[p] = 1; return ;    }    for (Edge *now = head[u]; now; now = now->next) if( dis[p|(1<
         
          v-1)] > dis[p]+now->d)     dis[p|(1<
          
           v-1)] = dis[p]+now->d, dfs(now->v, p|(1<
           
            v-1));}int ok[101], G[30][102], f[101];int main() {#ifndef ONLINE_JUDGE freopen("bzoj1003.in", "r", stdin);#endif scanf("%d%d%d%d", &n, &m, &K, &e); for ( int i = 1; i <= n; ++ i) ok[i] = (1 << m) - 1; for ( int i = 1, a, b, c; i <= e; ++ i) { scanf("%d%d%d", &a, &b, &c); head[a] = new Edge(b, c, head[a]); head[b] = new Edge(a, c, head[b]); } memset(dis, 0x3f, sizeof(dis)); dis[1] = 0; dfs(1, 1); scanf("%d", &e); for ( int i = 1, a, b, c; i <= e; ++ i) scanf("%d%d%d", &c, &a, &b), G[c][a]++, G[c][b+1]--; for ( int i = 2; i <= m; ++ i) for ( int k = 1; k <= n; ++ k) G[i][k] += G[i][k-1], ok[k] ^= ((G[i][k] != 0) << i-1); memset(f, 0x3f, sizeof(f)); f[0] = -K;// for ( int i = 1; i <= n; ++ i) printf("%d ", ok[i]); puts(""); // de bug// for ( int i = 1; i <= cnt; ++ i) printf("%d ", tp[i]); puts(""); // de bug// printf("%d\n", cnt); for ( int i = 1, l; i <= n; ++ i) for ( int k = 1; k <= cnt; ++ k) { l = i; for ( ; l && ((ok[l]&tp[k]) == tp[k]); -- l) f[i] = min(f[i], f[l-1]+dis[tp[k]]*(i-l+1)+K); } printf("%d\n", f[n]); return 0;}
           
          
         
        
       
      

---