Magic Transformation

iPig is training at the legendary Magic Pig Academy. After one week of theory and one week of basic magic, iPig learned many things about the world: it is composed of elements, and these elements can transform into one another (with energy conservation \(\ldots\)).

In today's test, iPig has already learned several magic spells that can transform one element into another – each spell consumes some energy. As one of the top students of PKU, iPig is required to transform many samples of element 1 into element \(N\) using the spells he has learned. To increase the challenge, the conversion process for each sample must be distinct (i.e. the sequence of spells used must be different in every sample). In order to conserve energy, iPig will choose the transformation processes in the order of increasing cost. Note that the transformation between two elements may have multiple available spells, and the conversions are directed (i.e. one‐way). In the transformation process, it is permitted to visit any element (including the starting element) multiple times; however, once the target element \(N\) is reached, the conversion process stops. Since iPig's total energy \(E\) is limited, he can only transform a finite number of samples. Your task is to determine, if iPig always chooses the cheapest as-yet-unused transformation path from element 1 to element \(N\), what is the maximum number of samples he can transform and what is the total energy consumed.

inputFormat

The first line contains three integers \(N\), \(M\), and \(E\), where \(N\) (the number of elements, numbered from 1 to \(N\)), \(M\) (the number of available magic spells), and \(E\) (the total available energy) satisfy \(1 \leq N \leq 100\), \(1 \leq M \leq 1000\), and \(1 \leq E \leq 10^5\) (constraints are for example purposes).

Each of the following \(M\) lines contains three integers \(u\), \(v\), and \(w\), indicating that there is a directed transformation (magic spell) from element \(u\) to element \(v\) with an energy cost of \(w\). You can assume all costs \(w\) are positive.

outputFormat

Output two integers separated by a space: the maximum number of samples that can be transformed, and the total energy consumed by these samples.

sample

4 5 50
1 2 5
2 4 10
1 3 10
3 4 5
2 3 2

3 42