N intervals are given in format of {start, end, cost} and i have to find out two non-overlapping intervals such that (Interval_1.end- Interval_1.start) +(Interval_2.end- Interval_2.start) is maximum and cost is minimum.

ex:-

for n=5

4 6 5

1 4 10

6 9 4

3 8 6

1 4 5

so, answer is {1,4},{6,9} as this is maximum and minimum cost for maximum range is 5+4=9