I saw that I can formulate single-source shortest path as the following linear program:
Given $G=(V,E)$ and $w\colon E\to R$ and with negative cycles, find $\max\,d(s,t)$ such that
\begin{align*} d(s,v) &\le d(s,u)+w(u,v) \quad \forall (u,v)\in E \\ d(s,s) &=0 \end{align*}
We want to find the shortest path from $s$ to $t$ so we are we maximizing $d(s,t)$?