401457: GYM100460 C Born for the Battle

Court magician Irdis asked for help his ex-student, the half-elf Desmond, who has been living exiled in the humans' lands for a long time. Desmond, realizing he cannot handle this alone, went to his friend, human warrior Thorwald, whom he had met during one of the military campaigns.

In order not to spend time for walking, Desmond decided to move over the astral plane, which contains n rooms. There are m astral corridors between the rooms, the j-th of which allows one instantly move between the a_j-th and the b_j-th rooms. The j-th corridor is also characterized by its disturbance energy c_j.

Desmond knows the scheme of astral corridors and has already numbered astral rooms so that after entering the astral he will be in the room number 1, and, to reach Thorwald, he needs to move to the room n and leave the astral from there.

But, just between us, this is only second astral journey for Desmond. The first time was when he entered the astral with his mentor Irdis, who told him about the technique of finding a suitable astral level, about the traffic density of magical energy and so on, but Desmond didn't understand anything that time and remembered from all the theory of magical transportations just a main conclusion: the travel over the astral plane does not require any mana, but to leave the astral one spends the amount of mana equal to the second greatest disturbance energy among all corridors he has passed while being in the astral. In the case you pass less than two corridors in the astral, no mana is required to leave it.

Of course, Desmond wants to spend as less mana as possible to travel to Thorvald — he will require all his powers when they will fight Deimos. So it's necessary to find, how much mana he needs to spend.

The first line contains two integers separated by the space: n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵) — the number of astral rooms and astral corridors, correspondingly.

Each of the next m lines contains three integers separated by the spaces: a_j, b_j and c_j (1 ≤ a_j < b_j ≤ n, 0 ≤ c_j ≤ 10⁹) — the description of the j-th corridor, which connects the a_j-th and the b_j-th rooms and has the disturbance energy c_j. There is at most one corridor between each pair of rooms.

Output one integer — the smallest amount of mana required to walk through the astral, entering it in the room 1 and leaving it from the room n. If such a journey is not possible at all, output  - 1.

3 2
1 2 3
2 3 4

3

4 4
1 2 7
2 4 8
1 3 2
3 4 1000

2