스키 코스

문제 정보

문제

이번 겨울에는 친구들과 스키장으로 놀러가기로 하였다. 스키장은 산자락에 지어져 있었고, 슬로프가 굉장히 다양했다. 볼거리가 많기로 유명한 슬로프들도 있었고, 보잘것 없는 슬로프도 있었다.

산에는 지점이 N개 있다. 모든 지점은 1 이상 N 이하의 정수로 번호가 매겨져 있다. 지점의 번호는 높이 순서에 따라 붙여진다. 지점의 번호가 증가하면 높이는 감소한다. 1번 지점이 가장 높고, N번 지점이 가장 낮다. 각 지점의 높이는 정해져있고, 모든 지점은 높이가 다르다. 일부 지점들 사이에는 스키를 타고 이동할 수 있는 슬로프가 있다.

스키를 한번 타기 시작하면 슬로프를 내려가는 것밖에 할 수 없다. 낮은 지점에서 높은 지점으로 올라가는 것은 불가능하다.

각 슬로프에는 흥미도가 매겨져 있고, 수치가 클수록 재미있는 슬로프이다. 반대로 너무 지루해서 흥미도가 음수인 슬로프도 있을 수 있다.

찬민이는 이러한 산에서 스키를 한 번 타려고 한다. 스키를 타고 슬로프를 따라 내려가기만 하고, 다른 지점으로 가기 위해서는 반드시 슬로프를 타고 내려가려고 한다. 하지만 체력이 좋지 않아서 슬로프는 최대 S개만 사용하고 싶어한다. 최대 S개의 슬로프만 사용한다고 할 때, 찬민이는 지나게 되는 슬로프의 흥미도의 합을 최대화 하고 싶다. 출발 지점은 찬민이가 목표를 달성하기 위해 원하는 대로 고를 수 있다. 경우에 따라서는 슬로프를 하나도 이용하지 않아도 된다.

입력

입력의 첫 줄에는 테스트 케이스의 개수를 의미하는 정수 T( \le 100)이 주어진다.
각 테스트 케이스의 첫 줄에 세 정수 N(1 \le N \le 50,000), M(0 \le M \le 100,000), S(1 \le S \le 100)가 빈 칸을 사이에 두고 주어진다.
N은 스키장에 있는 지점의 개수, M은 스키장에 있는 슬로프의 개수, S는 최대 이용 가능한 슬로프의 개수이다.
그 다음 M개의 줄에 세 정수 A_i, B_i, C_i가 빈 칸을 사이에 두고 주어진다.
(1 \le i \le M) 1 \le A_i < B_i \le N이고, -100,000 \le C_i \le 100,000이다.
A_i와 B_i는 슬로프가 잇는 두 지점의 번호를 의미하고, C_i는 해당 슬로프의 흥미도를 나타낸다.

출력

각 테스트케이스마다 최대 S 개의 슬로프를 연속으로 이용하여 얻을 수 있는 흥미도의 합의 최대값을 한 줄에 출력한다.

예제 입력

2
4 5 2
1 2 10
1 3 20
2 3 50
2 4 25
3 4 15
4 5 2
1 2 -5
1 3 20
2 3 50
2 4 25
3 4 -20

예제 출력

65
50

노트

9개의 댓글이 있습니다.