기내식 여행

N개의 도시가 동쪽에서 서쪽으로 1번부터 N번까지 차례대로 놓여 있다. 1번 도시는 가장 동쪽에 있고, N번 도시는 가장 서쪽에 있다.

당신은 이 도시들 중 최대 M개를 방문하는 여행을 계획한다. 여행은 반드시 1번 도시에서 시작해 N번 도시에서 끝나야 하며, 시작 도시와 도착 도시도 방문한 도시 수에 포함된다. 시차에 민감하므로 한 번 서쪽으로 이동한 뒤 다시 동쪽으로 돌아갈 수 없다. 따라서 여행 중에는 항상 도시 번호가 증가하는 방향으로만 이동해야 한다.

도시 사이를 이동할 때는 비행기를 타야 하지만, 모든 도시 쌍 사이에 항로가 있는 것은 아니다. 각 항로에는 제공되는 기내식의 점수가 정해져 있다. 사용할 수 있는 항로 정보가 주어질 때, 여행 중 먹는 기내식 점수 합의 최댓값을 구하라.

첫째 줄에 도시 수 N, 방문할 수 있는 최대 도시 수 M, 개설된 항로 수 K가 주어진다.

• 1 <= N <= 300
• 2 <= M <= N
• 1 <= K <= 100,000

다음 K개의 줄에는 항로 하나를 나타내는 세 정수 a, b, c가 주어진다. 이는 a번 도시에서 b번 도시로 가는 항로가 있으며, 그 항로의 기내식 점수가 c라는 뜻이다.

• 1 <= a, b <= N
• 1 <= c <= 10,000
• a = b인 입력은 주어지지 않는다.

도시 번호가 감소하는 방향의 항로가 입력될 수 있으며, 같은 두 도시 사이의 항로가 여러 번 주어질 수도 있다.

첫째 줄에 여행 중 얻을 수 있는 기내식 점수 합의 최댓값을 출력한다.