Highway Shortcuts

Every morning, Sejun drives along a highway of length D kilometers to get to school. The highway has many curves, making it difficult to drive. One day, Sejun learned about shortcuts that can make some parts of the highway shorter to travel.

Every shortcut is one-way from its start position to its end position. Sejun also cannot move in the direction where the highway position decreases.

Find the minimum distance Sejun must drive to reach school.

The first line contains the number of shortcuts N and the highway length D. N is a positive integer at most 12, and D is a positive integer at most 10,000.

Each of the next N lines contains the start position, end position, and length of one shortcut. Every position and length is a nonnegative integer at most 10,000, and each shortcut's start position is smaller than its end position.

Print the minimum distance Sejun must drive.