%!TeX program=lualatex

\documentclass[12pt]{article}
\input{structure.tex}
\renewcommand{\bottomtitlespace}{0.2cm}

\begin{document}

\renewcommand{\tl}{$1.5$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача C13. РАЗХОДКА}
\addauthor{Автор: Борис Михов}{2026}{03}{14}
\renewcommand{\header}{
	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
    	Национален кръг\\
    	Варна, 13 – 16 март 2026 г.\\
    	Група C, 7 – 8 клас, Ден 1 \\
}


Сашка се разхожда в Морската градина във Варна, като е изпаднала в беда -- купила си е дюнер и трябва да го опази от хищните гларуси. Това става още по-сложно, откакто в парка са въвели еднопосочно движение по алеите. Формално, Морската градина може да се представи като насочен, \textbf{ацикличен граф}, с $N$ върха, номерирани с числата от $1$ до $N$, и $M$ ребра. Всеки връх представлява една от $N$-те градини, като Сашка се намира в градина номер $1$. Ребрата в графа представляват алеите на парка, които свързват градините, и имат теглови коефициенти, показващи опасността дюнерът на Сашка да бъде иззет от гларус.

Въпреки опасността да остане гладна, Сашка все пак желае да направи пълноценна разходка, заради това тя иска да премине през път в графа, съдържащ точно $K$ ребра -- хем да се разходи, хем да не се преумори. Тъй като тя все пак иска да хапне, иска да избере алеите по такъв начин, че най-голямата опасност на някоя алея из разходката да бъде колкото се може по-малка. Възможно е и изобщо да няма път с точно $K$ ребра. 

Напишете програма \textbf{\texttt{walk}}, която определя дали съществува път с дължина $K$, започващ от връх $1$, и ако да, намира минималната опасност на такъв път, където опасността на един път е равна на максималната опасност на ребро в него. 

\subsection{Вход}
На един ред в стандартния вход са дадени целите положителни числа $N$, $M$ и $K$, съответно броят градини, броят алеи и търсената дължина на разходката. На останалите $M$ реда от входа са описани алеите. На $i$-тия ред от тях са дадени три цели положителни числа, съответно $v_i$, $u_i$ и $d_i$, които характеризират алея, насочена от градина $v_i$ към градина $u_i $ с опасност $d_i$.

\subsection{Изход}
На стандартния изход отпечатайте едно число, равно на минималната опасност на път, с дължина точно $K$ алеи, започващ от градина $1$. Ако няма такъв път, изведете $-1$.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
	\item $1 \leq N, K \leq 200\ 000$
	\item $1 \leq M \leq 500\ 000$
	\item $1 \leq v_i, u_i \leq N$
    \item $1 \leq d_i \leq 10^9$
\end{itemize}

\pagebreak
\subsection{Подзадачи}
\begin{table}[ht]
	\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|}
		\hline
		\textbf{Подзадача} & \textbf{Необходими подзадачи} & \textbf{Точки} & $N,K$ & $M$ & \textbf{Други ограничения}\\
		\hline
			$0$ & -- & $0$ & $-$ & $-$ & Примерните тестове. \\ 
		\hline
			$1$ & -- & $10$ & $\leq 10$ & $\leq 45$ & $-$ \\ 
		\hline
			$2$ & $0-1$ & $10$ & $\leq 20$ & $\leq 70$ & $-$ \\ 
		\hline
			$3$ & $0-2$ & $20$ & $\leq 1\ 000$ & $\leq 2\ 500$ & $-$ \\ 
		\hline
			$4$ & $0-3$ & $10$ & $\leq 6\ 000$ & $\leq 15\ 000$ & $-$ \\
		\hline
            $5$ & -- & $15$ & $\leq 2.10^5$ & $\leq 5.10^5$ & $d_i=1$ \\
		\hline
			$6$ & $0-5$ & $35$ & $\leq 2.10^5$ & $\leq 5.10^5$ & $-$ \\
		\hline
	\end{tblr}
	\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Пример 1}
\begin{table}[ht]
	\begin{tblr}{|X[20,l]|X[8,l]|X[72,j]|}
		\hline
		\textbf{Вход} & \textbf{Изход} & \textbf{Обяснение на примера} \\
		\hline
		\texttt
            {13 18 4\\
            1 2 4\\
            1 3 1\\
            2 4 6\\
            2 5 4\\
            2 6 2\\
            3 6 3\\
            3 10 4\\
            4 7 6\\
            5 8 5\\
            6 8 2\\
            10 11 6\\
            7 8 5\\
            11 12 7\\
            12 8 6\\
            7 9 5\\
            9 13 6\\
            13 8 1\\
            5 6 3} & 
            \texttt{4}
		& 
		{Една от оптималните рaзходки е означена на изображението. Всяка градина е изобразенa с окръжност, а всяка алея -- със стрелка.\\
		\begin{adjustbox}{width=0.65\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
			\includegraphics{graphMining1.png}
		\end{adjustbox}} \\
		\hline
	\end{tblr}
\end{table}

\pagebreak
\subsection{Пример 2}
\begin{table}[ht]
	\begin{tblr}{|X[20,l]|X[8,l]|X[72,j]|}
	\hline
		\texttt
            {4 4 3\\
1 2 5\\
1 3 6\\
3 2 4\\
1 4 1} & 
            \texttt{-1}
		& 
		{Липсва разходка с такава дължина.\\
		\begin{adjustbox}{width=0.4\textwidth, valign=t, center, margin=0cm 0.1cm 0cm 0.1cm}
			\includegraphics{graphMining2.png}
		\end{adjustbox}} \\
		\hline
	\end{tblr}
\end{table}

\end{document}
