DJ Gigs

Doug James is an up-and-coming DJ from Graphland who has had a tough time making it big. That changed when his latest EP Wiggly Waves became the first album in history to go both Platinum and Uranium. With his newfound popularity, Doug (a.k.a. DJ Polygon) has a problem most artists would envy: he must decide which of his many gig offers to accept.

There are $K$ venues in Graphland, connected by $R$ roads. The venues are numbered $1$ to $K$. Doug's house is venue $1$, and he is ready to leave or perform at time $t = 0$.

Doug has $G$ gig offers. The $i$-th gig is at venue $V_i$, runs during the time interval $[S_i, E_i)$ (inclusive start, exclusive end), and pays $M_i$ cryptocents. Doug cannot take multiple gigs at the same time, and he cannot take gigs while he is traveling between venues.

Doug is overwhelmed by his fame and the many gig requests, so he wants your help making as much money as possible.

The first line contains three integers $G$, $K$, and $R$: the number of gigs, the number of venues, and the number of roads. These satisfy $1 \leq G \leq 200000$, $1 \leq K \leq 100$, and $0 \leq R \leq \min(4000, K(K-1)/2)$.

Each of the next $R$ lines contains three integers $A_i$, $B_i$, and $T_i$, describing the $i$-th bidirectional road. It connects venues $A_i$ and $B_i$, and it takes $T_i$ time to travel the road in either direction. The values satisfy $1 \leq A_i, B_i \leq K$, $A_i \neq B_i$, and $1 \leq T_i \leq 1000000$. There is at most one road between any pair of venues.

Each of the next $G$ lines contains four integers $V_i$, $S_i$, $E_i$, and $M_i$. The $i$-th gig runs from time $S_i$ (inclusive) to $E_i$ (exclusive) at venue $V_i$ and pays $M_i$ cryptocents. These values satisfy $0 \leq S_i < E_i \leq 1000000000$ and $1 \leq M_i \leq 1000000$.

Output a single integer: the maximum number of cryptocents Doug can earn by taking the right gigs.

In the first sample, there are two gigs at venue $1$ and one gig at venue $2$. Doug can either play both gigs at venue $1$ for $11$ cryptocents, or spend the first $10$ units of time traveling to venue $2$ and play that gig for $33$ cryptocents. He chooses the latter.

In the second sample, Doug earns the most by staying at venue $1$ and playing both gigs for $70$ cryptocents.