Resonant Bridges

Time limit: 3000 msMemory limit: 256 MB

An archipelago has $N$ platforms connected by $M$ resonance bridges. The explorer starts on platform $1$ and wants to reach platform $N$ .

Each bridge can be crossed in either direction. The $i$ -th bridge has crossing time $t_i$ and pitch $p_i$ .

The explorer carries a tuning fork. After she crosses a bridge, the fork keeps the pitch of that bridge. Suppose she is standing on a platform after crossing at least one bridge, the fork currently keeps pitch $r$ , and she next wants to cross a bridge with pitch $q$ . Before crossing it, she must spend $\lvert q-r\rvert$ time retuning the fork, and then she spends the bridge's crossing time.

Before the first bridge is crossed, the fork has no pitch, so no retuning time is needed for the first bridge. The explorer may visit the same platform or cross the same bridge multiple times.

Find the minimum possible total time needed to reach platform $N$ . If $N = 1$ , the explorer is already there and the total time is $0$ .

Input

The first line contains two integers $N$ and $M$ ( $1 \le N \le 2 \times 10^5$ , ), the number of platforms and bridges.

Output

Print one line containing a single integer: the minimum possible total time to reach platform $N$ from platform $1$ .

If it is impossible to reach platform $N$ , print $-1$ instead.

Samples

Sample 1

Input

Output

One possible trip crosses from platform $1$ to platform $2$ , then from platform $2$ to platform $4$ . Its total time is $5 + \lvert 13 - 10\rvert + 5 = 13$ .

Resonant Bridges

Input

Output

Samples

Sample 1

Submit

Submissions

Sample 2

Sample 3