Syrjälässä on $n$ risteystä, joita yhdistää $m$ kaksisuuntaista tietä. Tiet voivat olla eripituisia. Mikä on pisin reitti johon kuuluu $k$ eri risteystä ja $k-1$ niitä yhdistävää tietä?

Syöte

Syötteen ensimmäisellä rivillä on kolme lukua, $n$, $m$ ja $k$, risteysten määrä, teiden määrä ja risteyksien määrä reitillä. Seuraavalla $m$:llä rivillä on jokaisella kolme lukua, $u_i$, $v_i$ ja $c_i$, jotka tarkoittavat että risteysten $u_i$ ja $v_i$ välillä on tie jonka pituus on $c_i$.

Tuloste

Tulosta kuinka pitkä on pisin reitti johon kuuluu tasan $k$ eri risteystä. Jos tällaista reittiä ei ole olemassa, tulosta 0.

Rajat

• $4 \le n \le 500$
• $1 \le m \le 2000$
• $4 \le k \le 6$
• $1 \le u_i, v_i \le n, u_i \neq v_i$
• $1 \le c_i \le 10^6$

Tehtävässä on 50 testitapausta.

Esimerkki

Syöte:

5 5 4
1 4 1
1 2 3
2 3 1
3 4 2
4 5 3

Tuloste:

7