Problem Description

You are given a simple connected undirected weighted graph with $ N $ vertices and $ M $ edges. The vertices are numbered from $ 1 $ to $ N $, and the edges are numbered from $ 1 $ to $ M $. Edge $ i $ connects vertex $ U_i $ and vertex $ V_i $ with weight $ W_i $. It is guaranteed that all edge weights are distinct.

Consider a path from vertex $ 1 $ to vertex $ N $ that allows vertex repetition. Let $C = (C_1, C_2, \ldots, C_k)$ be the sequence of weights of the edges traversed in order. Define a zigzag path as a path that satisfies one of the following conditions:

• $C_1 < C_2 > C_3 < \cdots$ or $C_1 > C_2 < C_3 > \cdots$. In other words, it satisfies one of the following:
• For any integer $i (1 \leq i \leq k - 1)$, if $ i $ is odd, then $ C_i < C_{i+1} $, and if $ i $ is even, then $ C_i > C_{i+1} $.
• For any integer $i (1 \leq i \leq k - 1)$, if $ i $ is odd, then $ C_i > C_{i+1} $, and if $ i $ is even, then $ C_i < C_{i+1} $.

Does a zigzag path exist? If it does, also find the minimum sum of the weights of the edges traversed.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ U_1 $ $ V_1 $ $ W_1 $ $ U_2 $ $ V_2 $ $ W_2 $ $\vdots$ $ U_M $ $ V_M $ $ W_M $

Output Format

If a zigzag path exists, output the minimum sum of the weights of the edges traversed in one line. If a zigzag path does not exist, output -1 in one line.

Sample Input and Output

Sample Input #1

5 5
1 4 4
3 5 2
2 3 6
2 5 1
3 4 3

Sample Output #1

14

Sample Input #2

4 3
1 2 4
2 3 6
3 4 8

Sample Output #2

-1

Sample Input #3

7 12
2 5 657831697
5 6 925940778
1 2 749029915
2 4 237755672
3 6 60634766
6 7 65418621
1 4 194639839
4 7 411656898
3 7 367905753
3 4 241675120
1 6 858592389
2 6 571202751

Sample Output #3

562368346

Notes/Hints

Constraints

• $2 \leq N \leq 10^5$
• $N - 1 \leq M \leq \min \left( \frac{N(N-1)}{2}, 10^5 \right)$
• $1 \leq U_i < V_i \leq N$
• $1 \leq W_i \leq 10^9$
• $(U_i, V_i) \neq (U_j, V_j) \ (i \neq j)$
• $W_i \neq W_j \ (i \neq j)$
• The graph given in the input is simple and connected.
• All inputs are integers.

Sample Explanation 1

Traversing edges in the order $ 1, 5, 3, 4 $ results in $ C = (4, 3, 6, 1) $, which satisfies the zigzag path condition. The sum of the weights in this case is $ 14 $. The path traversing edges $ 1, 5, 2 $ results in $ C = (4, 3, 2) $, which is not a zigzag path.

Sample Explanation 3

Original idea: primenumber_zz

见题面 Input 部分

见题面 Output 部分