% !TeX program=lualatex

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

\begin{document}

\renewcommand{\tl}{$1.6$ сек.}
\renewcommand{\ml}{$1024$ MB}
\problem{Задача A3. ПЪТЕШЕСТВИЕ}
\addauthor{Автор: Емил Инджев}{2026}{02}{14}
\renewcommand{\header}{
	XLII НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА\\
	Областен кръг, 14 февруари 2026 г.\\
	Група A – 11, 12 клас
}

Артър Дент е на междузвездно пътешествие из Млечния път, като неговата цел е да направи много дълго пътуване. Според Пътеводителя, из галактиката ни има $N$ планети, които има смисъл да се посещават. Между някой двойки от тях има редовни насочени (космически) полети (т.е. от планета $A$ може да се пътува към планета $B$, но обратното не е задължително). Някои от полетите са безплатни, но други се заплащат с кредити (официалната валута на Млечния път). А освен това има и субсидирани полети (за да окуражават туризма), които всъщност плащат кредити на пътниците си. Благодарение на Пътеводителя, Артър има списъка с всички $M$ съществуващи полети и цените им (където считаме, че субсидираните полети имат отрицателни цени).

В началото на пътешествието си, Артър разполага с баланс от $10^{50}$ кредита и може да си избере от коя планета да започне. След това той иска да пътува с поредица полети (като може да повтаря планети или полети колкото пъти поиска). При всяко пътуване цената на полета се приспада от баланса му, а в случая на субсидиран полет, субсидията се добавя към баланса му. Балансът му никога не може да стане отрицателен (ако би станал отрицателен, Артър няма да може да пътува със съответния полет). Целта на Артър е да пътешества много дълго време или по-точно да се вози на общо $10^{100}$ полета без да засяда в планета (засяда в планета, ако от нея не тръгва нито един полет, който Артър може да плати).

Помогнете на Артър, като напишете програма \textbf{\texttt{trip}}, която по зададени налични полети определя дали неговата цел е изпълнима, или не.

\subsection{Вход}

На първия ред от стандартния вход се въвеждат две цели числа: $N$ и $M$. На всеки от следващите $M$ реда се въвеждат по три числа, описващи един полет: $A_i$, $B_i$ и $C_i$ -- начална планета, крайна планета и цена (отрицателна за субсидирани полети). Гарантирано е, че всеки полет е между различни планети и няма два полета, които да имат едновременно еднаква начална и крайна планета.

\subsection{Изход}

На стандартния изход изведете дали целта на Артър е изпълнима: $1$, ако е, $0$, ако не е.

\subsection{Ограничения}
\vspace{0.1em}
\begin{itemize}
\item $1 \leq N \leq 5 \times 10^3$
\item $1 \leq M \leq 2 \times N$
\item $0 \leq A_i, B_i < N$
\item $-10^9 \leq C_i \leq 10^9$
\end{itemize}

\newpage
\subsection{Подзадачи}
\begin{table}[H]
\begin{tblr}{|Q[c,m]|Q[c,m]|Q[c,m]|Q[c,m]|X[c,m]|}
\hline
\textbf{№} & \textbf{Точки} & \textbf{\makecell{Необходими\\подзадачи}} & $N$ & \textbf{Други ограничения}\\
\hline
$0$ & $0$ & $-$ & $-$ & Примерните тестове. \\
\hline
$1$ & $9$ & $-$ & $\le 5 \times 10^3$ & Няма платени полети: $C_i \leq 0$. \\
\hline
$2$ & $10$ & $-$ & $\le 5 \times 10^3$ & Няма субсидирани полети: $C_i \geq 0$. \\
\hline
$3$ & $16$ & $-$ & $\le 500$ & Ако отговорът е да, има начин балансът да достигне поне $2 \times 10^{50}$ кредита. \\
\hline
$4$ & $8$ & $3$ & $\le 5 \times 10^3$ & Ако отговорът е да, има начин балансът да достигне поне $2 \times 10^{50}$ кредита \\
\hline
$5$ & $24$ & $-$ & $\le 5 \times 10^3$ & Няма начин балансът да достигне повече от $2 \times 10^{50}$ кредита. \\
\hline
$6$ & $25$ & $3$ & $\le 500$ & -- \\
\hline
$7$ & $8$ & $0-6$ & $\le 5 \times 10^3$ & -- \\
\hline
\end{tblr}
\caption*{Точките за дадена подзадача се получават само ако се преминат успешно всички тестове, предвидени за нея и необходимите подзадачи.}
\end{table}
\FloatBarrier

\subsection{Примери}
\begin{table}[H]
\begin{tblr}{width=0.6\textwidth, colspec={|l|l|X[j]|}}
\hline
\textbf{Вход} & \textbf{Изход} & \textbf{Илюстрация на примера} \\
\hline
\texttt{\makecell[lt]{6 7\\
0 1 -3\\
0 2 -5\\
0 4 0\\
1 2 -4\\
2 3 2\\
3 0 4\\
5 2 2}} &
\texttt{1} &
{\begin{minipage}[t]{\linewidth}
	\vspace{-0.2cm}
	\begin{adjustbox}{width=\textwidth, valign=t, center}
		\includesvg[inkscapelatex=false]{example1}
	\end{adjustbox}
	\vspace{0.1cm}
\end{minipage}} \\
\hline
\texttt{\makecell[lt]{6 7\\
0 1 -1\\
0 2 -2\\
0 4 1\\
1 2 3\\
2 3 -3\\
3 0 6\\
5 2 -1}} &
\texttt{0} &
{\begin{minipage}[t]{\linewidth}
	\vspace{-0.2cm}
	\begin{adjustbox}{width=\textwidth, valign=t, center}
		\includesvg[inkscapelatex=false]{example2}
	\end{adjustbox}
	\vspace{0.1cm}
\end{minipage}} \\
\hline
\end{tblr}
\end{table}

\end{document}
