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