Problem F
Ginger Candy

Mr. G is one of the most excellent students in North River High School for Gifted Students. Despite having impressive performance in a programming competition and making it to the next round, he was not totally happy since his best friend did not get such a great achievement. In order to appease the poor girl, Mr. G has to deal with a very hard challenge: Buy her some ginger candies!

The road system in North River province consists of $N$ junctions and $M$ bidirectional roads. Junctions are numbered from $1$ to $N$, and roads are numbered from $1$ to $M$, inclusive. On the $i^{th}$ road, which connects two junctions $u_ i$ and $v_ i$, there is a shop in which Mr. G can buy $c_ i$ ginger candies. No two roads have the same number of candies. Mr. G wants to meet his friend at some junction, travel through several roads without visiting the same road twice, buy all candies on those roads, and finish at the same junction where he starts.

Using his humble knowledge in Physics, Mr. G calculates the amount of energy he needs to spend as follow: Let $L$ be the maximum number of candies he buys in one road, and $K$ be the number of roads he passes through. The amount of energy he needs to spend is $L^2+\alpha K$, where $\alpha $ is some constant he has already known.

Help him to satisfy his friend with the minimum amount of energy.

Input

• The first line contains three integers $N$, $M$, $\alpha $, the number of junctions, the number of roads and the predefined constant Mr. G uses to calculate the amount of energy, respectively ($1 \leq N \leq 10^5$, $1 \leq M \leq 2 \times 10^5$, $1 \leq \alpha \leq 20$).

• In the next $M$ lines, each contains three integers $u$, $v$, $c$ ($1 \leq u \leq N$, $1 \leq v \leq N$, $10^6 \leq c \leq 10^9$), meaning that there is a road connecting two junctions $u$ and $v$, which sells $c$ ginger candies.

It is guaranteed that all $c$ in the above $M$ lines are distinct.

Output

Write one integer denoting the minimum amount of energy Mr. G has to spend. If there is no route satisfying the condition, output Poor girl instead.

7 7 10
1 2 1000000
2 3 2000000
3 4 3000000
4 5 4000000
5 6 5000000
6 7 6000000
7 1 7000000

49000000000070

6 6 7
1 3 1000000
3 5 3000000
5 1 5000000
2 4 2000000
4 6 4000000
6 2 6000000

25000000000021

5 4 1
1 2 22081999
1 3 28021999
2 4 19992208
2 5 19992802

Poor girl