스키 코스

문제 정보

문제

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

산에는 지점이 \(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개의 댓글이 있습니다.