U396074 外送

晓莱最近暑假假期临近，他准备去送外卖，齐国的城镇道路图可以理解为一张 $n$ 个点 $m$ 条边的有向图， 现在外卖平台上已经有 $q$ 个配送任务，任务的描述形式为 ($ s_i , t_i , l_i , r_i$ )， 即需要从点$s_i $送到 $t_i$， 在时刻 $l_i$ 之后（包括 $l_i$ ）可以在 $s_i$ 领取货物，需要在时刻 $r_i$ 之前（包括 $r_i$）送达 $t_i$ ，每个任务只需完成一次。 边权代表通过这个道路需要消耗的时间。 在时刻 $0$ 晓莱在点 $1$ 上，求他最多能完成多少个配送任务。 在整个过程中，可以认为领货跟交货都是不消耗时间的，时间只花费在路程上。在一个点逗留也是允许的。

第一行包含三个正整数， 分别是 $n , m , q$ 。 接下来 $m$ 行，每行三个正整数 $u_i , v_i , c_i$ ，表示有一条从 $u_i$ 到 $v_i$ 耗时为 $c_i$ 的有向边。 接下来 $q$ 行，每行四个正整数 $s_i , t_i , l_i , r_i$ ，描述一个配送任务。

一个整数，表示最多能完成的任务数量。

提示：晓莱可以在时刻 $1$ 到达点 $2$ ，领取第二个货物后在时刻 $2$ 到达点 $3$ 后交货，逗留到时刻 $4$ ，领取第三个货物，在时刻 $4$ 到达点 $4$ 并交货。 对于 $20\%$ 的数据，保证 $2\leq n\leq 20, 1\leq m\leq 100, 1\leq q\leq 5,1\leq u_i,v_i\leq n, 1\leq c_i\leq 1000,1\leq s_i,t_i\leq n, 1\leq l_i\leq r_i\leq 10^3$。 对于$100\%$ 的数据，保证 $2\leq n\leq 20, 1\leq m\leq 400, 1\leq q\leq 10,1\leq u_i,v_i\leq n, 1\leq c_i\leq 20000,1\leq s_i,t_i\leq n, 1\leq l_i\leq r_i\leq 10^6$。