터치 앤 리턴

용준이는 터치 앤 리턴이라는 게임을 하기로 했습니다.

게임의 규칙은 다음과 같습니다.

1. 체력을 소모하여 현재 있는 지점에서 통로로 연결된 다른 지점으로 이동할 수 있습니다. 단, 현재 갖고 있는 체력보다 통로의 체력 소모량이 더 큰 경우 이동할 수 없습니다.
2. 매 턴 용준이는 $1$번 지점에서 출발하여 원하는 만큼 지점을 방문한 뒤, 다시 $1$번 지점으로 돌아와야 합니다. 한 턴 내에서 같은 지점을 중복하여 방문할 수 있습니다.
3. $1$번 지점에 돌아오면, 무조건 $($이번 턴에 방문한 서로 다른 지점의 수 $- 1)^2$ 로 계산된 점수를 획득하고, 한 턴이 종료됩니다.
4. 체력이 $0$ 미만이 되는 순간, 게임이 종료됩니다. 즉, 체력이 부족하여 원점에 돌아오지 못한 경우, 점수를 획득할 수 없습니다.

예를 들어, 경로가 $1 → 2 → 3 → 4 → 3 → 5 → 3 → 2 → 1$ 이라면, 방문한 지점은 ${1,2,3,4,5}$이고, $1$번 지점을 제외하면 $4$개의 지점이므로 획득하는 점수는 $4^2 = 16$점이 됩니다.

지점의 이름은 $1$부터 $N$까지의 정수이며, 지점 간 이동에는 체력이 소모됩니다. 그리고, 주어진 체력 $K$ 이내에서, 이러한 경로 탐색을 여러 번 할 수 있습니다.

목표는 주어진 체력으로 얻을 수 있는 최대 점수를 구하는 것입니다. 이때, 모든 체력을 사용할 필요는 없습니다.

첫째 줄에 지점의 수 $N$, 두 지점을 잇는 통로의 수 $M$, 용준이의 체력 $K$가 주어집니다. ($2 \leq N \leq 20; 1 \leq M \leq 300\,000; 1 \leq K \leq 100\,000;$ $N$, $M$, $K$는 정수)

다음 $M$개 줄에 $a$ $b$ $c$가 주어지는데, 이는 지점 $a$와 지점 $b$ 사이의 통로를 이용할 경우 소모되는 체력이 정수 $c$인 통로를 나타냅니다. 이 통로에서는 양방향 통행이 가능합니다. ($1 \leq a, b \leq N; a \neq b; 1 \leq c \leq 100\,000$)

주어진 체력으로 얻을 수 있는 최대 점수를 출력해 주세요.