Problem Description
There are n places (numbered 1,2,...,n), and at any second X, in place A, it will appear k robots. Now you have normal weapons. If at the second X and you are in place A, you will distroy those k robots. Otherwise, you have a special weapon (named O4), if you at second X in the place A and use O4, you will destroy all the robots which appear in the place adjoining to A (OF COUSE include the place A). You move from place A to B (B adjoins to A) must use some second;
Now you have T second ,and ask you two questions:
Input
First line: n, m, T. (n is the number of place, m is the number of roads between place, T is the seconds you have), n ≤ 100, m ≤ 2500, t ≤ 1000;
From 2 to m + 1 line: every line contains 3 integers, P, Q, D, indicating that moving from place P to place Q will use D seconds (the roads are undirection);
Next every line contains 3 integers, X, A, K, indicating at the X second, the place A will appear K robots;
The last line contains three "0" indicating that the case is end;
Output
The answer to the two question, separate by one space.
Sample Input
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
Sample Output
32 29