Sailboat

Winnie the Pooh set out on a sailing trip with Tigger. Tigger is an experienced sailor and steers the boat, while Pooh, a landlubber, is a little scared. Every time the boat changes its heading, the wind changes the boat's heel (tilt) angle. Each such change makes Pooh cry out loudly: the larger the change in heel, the louder he shouts, but the more of an adventure he collects. Pooh's total thrill from the trip is the sum of the squares of every heel change between two consecutive segments. Help Tigger maximize it.

The trip starts at Piękna Góra and ends at Sztynort. Turns may be made only at the marked buoys. From every buoy you may sail only along fixed routes, and every route always leads to a buoy with a higher number than the current one. Buoy number $1$ stands at the start (Piękna Góra) and buoy number $n$ stands at the finish (Sztynort). Every route segment joining two buoys has a fixed heel value given in the input. Because the boat must motor in and out of the harbor, every segment leaving the start and every segment entering the finish has heel $0$.

If the segments traversed in order have heels $x_1, x_2, x_3, \dots, x_k$, then

$\sum_{i=1}^{k-1}(x_i - x_{i+1})^2$

is Pooh's total thrill. Your task is to compute the maximum possible value of this sum.

Write a program that:

• reads the description of the routes from standard input,
• computes the maximum thrill of the trip,
• writes the result to standard output.

The first line contains two integers $n$ and $m$ separated by a single space, where $1 \le n \le 200000$ and $1 \le m \le 500000$.

Each of the next $m$ lines contains three integers $a$, $b$, and $w$ separated by single spaces. The numbers $a$ and $b$ are the buoys joined by this segment, with $1 \le a < b \le n$. The number $w$ is the heel of the boat on this segment, with $-100000 \le w \le 100000$. If $a = 1$ (the start) or $b = n$ (the finish), then $w = 0$.

Print a single integer: the maximum thrill Pooh can get from the trip.