409857: GYM103811 A Allowance Exhaustion

Melissa lives in London. She has been longing for a chance to explore London, but she has been trapped in her desk by large piles of documents in front of her. Today she finally gets $$$T$$$ minutes from her manager to travel around, after which she must come back to the office.

Junctions and streets in London can be modelled as a simple undirected graph of $$$N$$$ nodes and $$$M$$$ edges. Nodes are numbered from 1 to $$$N$$$ inclusive. For simplicity, let's assume it takes one minute to traverse any street. Yet, different streets bring on different levels of satisfaction to Melissa. The final satisfaction is the sum of the satisfaction levels of each street she has gone through. If Melissa passes through the same street twice, that street will contribute twice the satisfaction. As a rational agent, she would like to maximise her final satisfaction.

Just before Melissa steps out of the office, her manager has presented her with an unreasonable restriction: She must come back to the office after exactly $$$T$$$ minutes have elapsed. Throughout the $$$T$$$ minutes, she must not stay still at any junction/street. In other words, she must choose a route consisting of exactly $$$T$$$ edges, starting and ending at her office (located on node 1).

Help Melissa calculate the maximum satisfaction she could possibly attain. If no such route exists, tell her it's impossible.

Please be aware that London was brought up by sound people - There won't be any street directing back to itself nor multiple streets between the same pair of junctions.

The first line consists of 3 integers, $$$N$$$, $$$M$$$ and $$$T$$$, which corresponds to the number of nodes, edges in the graph, and the number of minutes that Melissa has. ($$$1\leq N\leq 1000$$$, $$$0\leq M\leq 10^4$$$, $$$0\leq T\leq 10^9$$$)

Input is then followed by $$$M$$$ lines, each having 3 integers, $$$u$$$, $$$v$$$ and $$$w$$$, denoting that an edge exists between $$$u$$$ and $$$v$$$, and going through which would yield a satisfaction level of $$$w$$$. ($$$0\leq w\leq 10^9$$$)

Output a single integer: the maximum satisfaction possible. If no route fits in the restrictions, output $$$-1$$$ instead.

5 6 6
1 2 2
1 4 4
2 3 6
2 5 0
3 4 5
3 5 9

36

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

38

5 6 3
1 2 2
1 4 4
2 3 6
2 5 0
3 4 5
3 5 9

-1

In the first sample, one best route is $$$1\to 4\to 3\to 5\to 3\to 4\to 1$$$.

In the second sample, one best route is $$$1\to 2\to 5\to 3\to 5\to 3\to 4\to 1$$$.