Given a tree T containing N nodes numbered [1,2..,N] rooted at node 1 and M edges. Each edge has a value associated with it.You are also given a number K. You need to find the maximum weight you can collect in K-steps .When you traverse an edge, it is counted as 1 step.

Note:
1. you should start from root node.
2. you can traverse an edge from parent to child or child to parent.
3. you can traverse an edge multiple times.
4. weights of edges are always positive integer.
Input format:

1. first line contain N,M,K i.e number of nodes, number of edges, number of steps respectively.
2. next M lines contain three integers a,b,c i.e there is an edge between 'a' and 'b' with weight 'c'.

Output format:

maximum weight collected in K-steps.

Example:-
Input:
6 5 3
1 2 5
1 3 6
2 4 15
2 5 1
3 6 11

Output: 35

Explanation:

Traversal for max. weight collection: [1-2-4-2]. Thus weight collected 5+15+15=35

How to solve this question? Plz Help. Thanks in advance.