Kuponi

Podano je železniško omrežje v obliki neusmerjenega uteženega grafa z $N$ vozlišči in $E$ povezavami. Vozlišča predstavljajo mesta, povezave pa direktne dvosmerne železniške povezave med njimi. Mesta so oštevilčena od $1$ do $N$, pripotovati pa želite iz mesta $1$ v mesto $N$. Za potovanje po izbrani povezavi morate plačati ceno vozovnice $C_{x,y}$, ki predstavlja ceno za neposredno vožnjo med mestoma $x$ in $y$.

Ker ste redni uporabnik železnice, imate na voljo $K$ kuponov. Z uporabo kupona lahko prepolovite ceno povezave. Na vsaki povezavi lahko uporabite največ en kupon. Napišite program, ki bo izračunal najmanjšo ceno potovanja.

Omejitve podatkov:

• $1 \leq N \leq 1000$
• $1 \leq E \leq 10^5$
• $0 \leq K \leq 10$
• $0 \leq C_{x,y} \leq 10^9$, vse vrednosti $C_{x,y}$ so sode.

Vhodni in izhodni podatki:

V prvi vrstici so s presledkom ločena števila $N$, $E$ in $K$. Sledi $E$ vrstic, ki predstavljajo železniške povezave s celimi števili $x$, $y$ in $C_{x,y}$. Pri tem sta $x$ in $y$ mesti, med katerima poteka povezava, $C_{x,y}$ pa je cena vozovnice na tem odseku.

Izpišite iskano najmanjšo ceno potovanja, ki jo lahko dosežete z uporabo kuponov.

Primer vhoda:

6 7 1
1 5 8
2 6 6
3 4 14
4 5 16
5 2 8
1 4 6
6 3 4

Pravilen izhod:

17