\textit{Michiel Adriaenszoon de Ruyter} is the most famous admiral in Dutch history and is well known for his role in the Anglo-Dutch Wars of the \textbf{17}^th century. De Ruyter personally commanded a flagship and issued commands to allied warships during naval battles. In De Ruyter’s time, graph theory had just been invented and the admiral used it to his great advantage in planning his naval battles. Waypoints at sea are represented by vertices, and possible passages from one waypoint to another are represented as directed edges. Given any two waypoints \textbf{W_1} and \textbf{W_2}, there is at most one passage\textbf{W_1} → \textbf{W_2}. Each directed edge is marked with the number of cannonballs that need to be fired in order to safely move a ship along that edge, sinking the enemy ships encountered along the way. One of De Ruyter’s most successful tactics was the De Ruyter Manoeuvre. Here, two warships start at the same waypoint, and split up and fight their way through the enemy fleet, joining up again at a destination waypoint. The manoeuvre prescribes that the two warships take disjunct routes, meaning that they must not visit the same waypoint (other than the start and end-points), or use the same passage during the battle. Being Dutch, Admiral De Ruyter did not like to waste money; in \textbf{17}^th century naval warfare, this meant firing as few expensive cannonballs as possible. \includegraphics{https://static.e-olymp.com/content/5e/5e5cbe27e5a571d24584606f49f09959e3046d8f.jpg} Figure 1: A particular instance of De Ruyter’s tactic, visualised as a graph. Two ships (‘red’ and ‘blue’) move from a shared starting point (\textbf{1}) to a shared endpoint (\textbf{6}). The red ship’s route is \textbf{1} → \textbf{3} → \textbf{6} (firing \textbf{33} canonballs along the way); the blue ship’s route is \textbf{1} → \textbf{2} → \textbf{5} → \textbf{4} → \textbf{6} (firing \textbf{53} canonballs along the way). In total, \textbf{86} canonballs are fired during the manoeuvre. Except for the start- and end-point, no vertices or edges are visited by both ships. \InputFile For each test case, the input consists of: \begin{itemize} \item line containing two integers \textbf{v }(\textbf{3 }≤ \textbf{v }≤ \textbf{1000}) and \textbf{e }(\textbf{3 }≤ \textbf{e }≤ \textbf{10000}), the number of waypoints and passages, respectively. \item Then \textbf{e }lines follow: for each passage, a line containing three integers: \end{itemize} \begin{enumerate} \item \textbf{a_i} (\textbf{1 }≤ \textbf{a_i} ≤ \textbf{v}), the starting-point of a passage, which is represented by a waypoint; \item \textbf{b_i} (\textbf{1 }≤ \textbf{b_i} ≤ \textbf{v}) and (\textbf{a_i} ≠ \textbf{b_i}), the end-point of a passage, which is represented by a waypoint. All passages are directed passages; \item \textbf{c_i} (\textbf{1 }≤ \textbf{c_i} ≤ \textbf{100}), the number of cannonballs that are fired when travelling along this passage. \end{enumerate} The starting waypoint is \textbf{1 }and the destination waypoint is \textbf{v}. There are always at least two disjunct routes from waypoint \textbf{1 }to waypoint \textbf{v}. \OutputFile For each test case, the output consists of a single positive integer: the smallest possible sum of cannonballs fired by both ships when reaching the destination waypoint.