The Shortest Distance Problem

In the lives of Xiaoming and Xiaohong, there are N key nodes. There are M events, each represented by a triple \( (S_i, T_i, W_i) \). An event from node \( S_i \) to node \( T_i \) reduces the distance between them by \( W_i \) (i.e. the effect of the event is to subtract \( W_i \) from the current distance).

The nodes form a network where node 1 represents Xiaoming and node N represents Xiaohong. Other nodes represent stages in their journey. You may choose any event as long as it is adjacent to the current node. Your task is to compute the possible shortest distance between Xiaoming and Xiaohong by selecting a sequence of events.

Mathematically, if you start from a distance of 0 at node 1, every time you take an event from \( S_i \) to \( T_i \), the distance becomes:

$$ distance[T_i] = distance[S_i] - W_i $$

Your goal is to minimize the distance at node \( N \). It is guaranteed that no sequence of events can be chosen infinitely to reduce the distance arbitrarily (i.e. no negative cycles affecting the result).

inputFormat

The first line contains two space-separated integers, N and M, which denote the number of nodes and events respectively.

Each of the next M lines contains three space-separated integers \( S_i \), \( T_i \), and \( W_i \), describing an event from node \( S_i \) to node \( T_i \) with a reduction value of \( W_i \).

You may assume that 1 \( S_i, T_i \) \( \leq N \) and all integers are valid.

outputFormat

Output a single integer, the shortest possible distance between node 1 (Xiaoming) and node N (Xiaohong) after selecting events optimally.

sample

4 4
1 2 3
2 4 2
1 3 4
3 4 1

-5