== include(page="template/taskheader" task_id="curcani") ==

Poveste şi cerinţă...

Aflând de intenţiile lui Rick de a se transforma într-un curcan de Ziua Recunosţintei pentru a nu mai fi marcat drept terorist, preşedintele Curtis se hotărăşte să trimită o armată de curcani pe urmele lui. Reşedinţa preşedintelui se află în oraşul cu numărul $1$, iar Rick se află în oraşul $N$. Oraşele sunt conectate între ele prin $M$ străzi unidirecţionale de diferite lungimi. Curcanii se află iniţial în nodul $1$ şi vor să ajungă la Rick, adică în nodul $N$, pe cel mai scurt drum.
Rick are posibilitatea să mărească lungimile muchiilor pentru a încetini armata de curcani, dar cu un anumit cost. Mai exact, costul pentru a mări muchia $i$ cu $j$ unităţi este $v[i][j]$. Pentru a căştiga timp, Rick vrea să mărească muchiile grafului astfel încât *lungimea celui mai scurt drum intre $1$ şi $N$ să fie cu $K$ unităţi mai mare decât era iniţial*. În plus, ştim că $v[i][j-1] - v[i][j-2] <= v[i][j] - v[i][j-1].$

h2. Date de intrare