Jimin's Farm Tour Season II

Jimin visits the home of Jeongmun, a large landowner. Jeongmun wants to show Jimin the N farms he manages. The farms are numbered from 1 to N, and there are M bidirectional roads between them.

They are currently at farm 1. Jimin wants to visit farm N and then return to farm 1. However, Jimin plans to plant a mine on every road he passes, so he does not want to use any road that has already been used.

Given the time needed to traverse each road, find the minimum total time required to start at farm 1, visit farm N, and return to farm 1. The same road may not be used more than once.

The first line contains two positive integers N and M. N is the number of farms, and M is the number of roads. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000)

Each of the next M lines contains three positive integers P, Q, and L describing a road. This means there is a road between farm P and farm Q, and traversing it takes L time. (1 ≤ L ≤ 35,000)

The input is guaranteed to contain a valid round trip satisfying the condition.

Output the minimum time needed to start at farm 1, visit farm N, and return to farm 1.