A. Phoenix Against the Monsters
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Phoenix, a skilled warrior, has been assigned an important mission: to deliver critical information from the city of Nagpur to the stronghold of Mumbai. The journey is filled with danger, as monsters guard the roads connecting different cities. Each road has a certain number of monsters that Phoenix will need to fight.

Phoenix has a special ability that he can use once during his journey. This ability allows him to halve the number of monsters (rounded down to the nearest whole number) on either one road or two consecutive roads. By using this ability wisely, Phoenix can reduce the total number of monsters he has to fight and increase his chances of completing the mission.

Your task is to help Phoenix find the minimum total number of monsters he must face to deliver the information to Mumbai.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 10^5$$$ and $$$1 \leq m \leq 2 \cdot 10^5$$$): the number of cities and the number of roads connecting them. The cities are numbered $$$1,$$$ $$$2,$$$ $$$\ldots$$$ $$$n$$$. City $$$1$$$ is Nagpur, and city $$$n$$$ is Mumbai.

After this, there are $$$m$$$ lines describing the roads. Each line contains three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n$$$ and $$$1 \leq w \leq 10^9$$$): a road starts at city $$$u$$$, ends at city $$$v$$$, and has $$$w$$$ monsters on that road. Each road is unidirectional.

You can assume that it is always possible to get from Nagpur to Mumbai.

Output

Output a single integer — the minimum total number of monsters Phoenix must face to deliver the information from Nagpur to Mumbai.

Examples
Input
5 6
1 2 5
2 3 2
3 5 1
1 4 10
4 5 5
2 4 3
Output
4
Input
2 1
1 2 5
Output
2
Input
6 8
1 2 7
1 3 4
2 4 3
2 5 2
3 4 6
4 6 2
5 6 4
3 5 8
Output
6
Note
  • In the first sample, Phoenix starts in City $$$1$$$ (Nagpur).
  • He takes the road to City $$$2$$$, which has $$$5$$$ monsters.
  • He then proceeds from City $$$2$$$ to City $$$3$$$, where the road has $$$2$$$ monsters.
  • From City $$$3$$$, he travels to City $$$5$$$ on a road with only $$$1$$$ monster.
  • Phoenix uses his special ability to halve the number of monsters on the roads between City $$$1$$$ and City $$$2$$$, and City $$$2$$$ and City $$$3$$$, reducing the monsters to $$$2$$$ and $$$1$$$ respectively.
  • This results in a total of $$$4$$$ monsters he must fight to deliver the information to City $$$5$$$ (Mumbai).
  • In the second sample, Phoenix must travel directly from City $$$1$$$ (Nagpur) to City $$$2$$$ (Mumbai) on a road with $$$5$$$ monsters. He uses his ability to halve the monsters on this road, reducing the count to $$$2$$$. Thus, Phoenix only faces $$$2$$$ monsters in total.