I. Wormholes
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Meryl and Roberto are currently on planet Gunsmoke and are trying to reach Pluto. They each leave Gunsmoke in a one-person space pod, and the only way they can travel between planets is by traveling through wormholes located around each planet. However, these wormholes highly unstable. Each wormhole can only be taken once before it collapses. Additionally, each wormhole causes a certain amount of damage to the space pod. Finally, wormholes only go in one direction. Due to the laws of physics, there cannot be multiple wormholes that start at the same planet and go to the same planet. Meryl and Roberto want to know whether it is possible for both of them to reach Pluto, and if so, what the least amount of total damage they can take on their way to Pluto.

Input

The first line contains $$$n$$$ ($$$2 \leq n \leq 2 \times 10^5$$$), the number of planets, and $$$m$$$, ($$$1 \leq m \leq 2 \times 10^5$$$) the number of wormholes. Planet 1 is Gunsmoke, and planet $$$n$$$ is Pluto. The following $$$m$$$ lines each contain an integer $$$a$$$ ($$$1 \leq a \leq n$$$), $$$b$$$ ($$$1 \leq b \leq n$$$), and $$$c$$$ ($$$1 \leq c \leq 10^9$$$). This represents a wormhole from planet $$$a$$$ to planet $$$b$$$ that causes $$$c$$$ damage to a space pod passing through it.

Output

If it is impossible for both Meryl and Roberto to reach Pluto, print out $$$-1$$$. Otherwise, print out the minimum possible total damage received to the two space pods.

Examples
Input
6 14
1 2 1
2 1 1
1 3 2
3 1 2
2 4 1
4 2 1
3 4 2
4 3 2
2 5 2
5 2 2
4 6 1
6 4 1
5 6 2
6 5 2
Output
10
Input
5 7
2 5 5
2 4 3
1 4 2
4 5 10
4 2 7
1 3 5
3 2 1
Output
23
Input
5 5
1 2 1
1 3 1
2 4 1
3 4 1
4 5 1
Output
-1