The army of United Nations launched a new wave of air strikes on terrorist forces. The objective of the mission is to reduce enemy’s logistical mobility. Each air strike will destroy a path and therefore increase the shipping cost of the shortest path between two enemy locations. The maximal damage is always desirable. Let’s assume that there are n enemy locations connected by m bidirectional paths, each with specific shipping cost. Enemy’s total shipping cost is given as ∑n ∑n c= path(i,j) i=1 j=1 Here path(i,j) is the shortest path between locations i and j. In case i and j are not connected, path(i,j) = L. Each air strike can only destroy one path. The total shipping cost after the strike is ′ noted as c . In order to maximized the damage to the enemy, UN’s air force try to find the maximal c′ − c. Input The first line of each input case consists of three integers: n, m, and L. 1 < n ≤ 100, 1 ≤ m ≤ 1000, 1 ≤ L ≤ 108. Each of the following m lines contains three integers: a, b, s, indicating length of the path between a and b. Output For each case, output the total shipping cost before the air strike and the maximal total shipping cost after the strike. Output them in one line separated by a space. Sample Input 4 6 1000 132 144 213 233 341 422 Sample Output 28 38