Minimum Travel Time in Fatigued Mountain Trails

You are given n mountains and m directed trails. Each trail connects two distinct mountains and takes a certain amount of time to traverse. However, due to fatigue, every time Xiao X traverses a trail, his fatigue increases so that the time to traverse any trail increases by 1 for each trail he has already passed.

More formally, if Xiao X takes a sequence of k trails with base travel times \(t_1,t_2,\dots,t_k\), then the actual time taken for the \(i\)-th trail is \(t_i + (i-1)\). Therefore, the total time cost of the route is \[ \sum_{i=1}^{k} \bigl(t_i + (i-1)\bigr) = \left(\sum_{i=1}^{k} t_i\right) + \frac{(k-1)k}{2}. \]

Xiao X starts at mountain \(1\) and wishes to reach mountain \(n\) (where the train station is located) in the minimum possible total time. If there is no way to reach mountain \(n\), output \(-1\).

inputFormat

The first line contains two integers \(n\) and \(m\) (number of mountains and trails). Each of the next \(m\) lines contains three integers \(u\), \(v\), and \(t\), representing a directed trail from mountain \(u\) to mountain \(v\) with a base travel time of \(t\).

\(1 \leq u,v \leq n\)

outputFormat

Output a single integer: the minimum total time required for Xiao X to travel from mountain \(1\) to mountain \(n\), taking into account the fatigue penalty. If it is impossible to reach mountain \(n\), output \(-1\).

sample

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

4