题目描述

鼹鼠一共在仓库中打了$\red{n}$个洞（用$\red{1}$至$\red{n}$编号），在这$\red{n}$个洞中，有些洞之间是连通的，你可以花费一定的时间从连通的一个洞口处跑到另一个洞口处，然而有些洞之间由于货物的堆 放等原因并不是连通的，也就是你并不能直接从不连通的一个洞口处跑到另一个洞口处。（但所有的连通关系都是双向的）当你在某一时刻正好在某个洞旁时，如果正好这个洞中有一只出现在洞口处，你就可以用手 中的武器（一把大锤）消灭这支鼹鼠，当你在某一时刻停留在某个洞穴处并使用大锤时，该洞当前出现的所有鼹鼠都将被消灭。你有$\red{t}$秒的时间来进行消灭鼹鼠的战斗，你也知道在这$\red{t}$秒内鼹鼠每次 出现的时间和位置。那么，你最多能消灭多少只鼹鼠呢？为了旧能多的消灭鼹鼠，$\red{dd_engi}$为你提供了一种超级武器：如果你在某个特定时刻在某个洞口处使用这个超级武器的话，那么这个洞以及与它直接有边相连的所有洞中此刻出现的鼹鼠都会被消灭掉。然而，这个超级武器只能使用一次。你需要编程求出的就是：用或者不用这个超级武器，你分别能消灭多少只鼹鼠？注意：你可以不用完你所给的时间，而且可以有 一些时间你并没有来回跑动而是仅仅停在某个洞的旁边。

输入格式

第一行为三个用空格隔开的整数$\red{n}$、$\red{m}$、$\red{t，}$分别表示鼹鼠洞的个数和连通的边数以及你的时间$\red{t}$。

以下$\red{m}$行，每行有三个用空格隔开的整数$\red{i}$、$\red{j}$、$\red{k，}$表示编号$\red{i}$、$\red{j}$的两个鼹鼠洞是双向连通的，从一个运动到另一个需要花费的时间为$\red{k}$。

以下每行有三个用空格隔开的整数，第一个整数表示描述的这些鼹鼠将于第几秒末出现，第二个整数表示描述的这些鼹鼠出现的洞的编号，第三个整数表示这次将会出现的鼹鼠的数量。以三个整数$\red{0}$表示输入的结束。

输入文件的结尾是一个回车$\red{/}$换行符。

输出格式

只需输出两个用空格隔开的整数，分别表示用和不用超级武器能消灭的最多鼹鼠数。最后以一个回车$\red{/}$换行符结尾。

样例

输入样例

3 2 10
1 2 1
2 3 2
1 1 1
2 2 2
3 3 3
4 1 4
2 3 3
4 2 2
6 1 4
8 2 3
10 2 2
9 1 1
7 1 5
3 2 2
8 1 8
0 0 0

输出样例

32 29

提示

$\red{n<=100}$

$\red{t<=1000}$