Tại Hy Lạp cổ đại, có $n$ thành phố được kết nối bởi $m$ con đường hai chiều. Có thể đi đến bất kỳ thành phố nào từ một thành phố khác bằng cách di chuyển qua các con đường (có thể thông qua một vài thành phố trung gian). Giữa hai thành phố bất kỳ có tối đa một con đường và mỗi con đường kết nối hai thành phố phân biệt. Con đường thứ $i$ có độ dài $c_i$.

Heracles đang khẩn cấp phải thực hiện 12 kỳ công theo chỉ dẫn của vua Eurystheus. Các kỳ công này phải được thực hiện tại 12 thành phố nhất định của Hy Lạp cổ đại. Hiện tại, Heracles đang ở thành phố Mycenae, nơi không nằm trong số 12 thành phố này. Để thực hiện các kỳ công nhanh nhất có thể, Heracles muốn xây dựng một kế hoạch di chuyển tối ưu, theo đó anh phải ghé thăm 12 thành phố cần thiết và quay trở lại Mycenae trong thời gian ngắn nhất có thể.

Hãy giúp Heracles xác định thời gian tối thiểu cho chuyến đi. Heracles đi qua một con đường có độ dài $c_i$ trong thời gian $c_i$. Mỗi con đường có thể được đi qua số lần tùy ý theo bất kỳ hướng nào, và bất kỳ thành phố nào cũng có thể được ghé thăm số lần tùy ý. Thứ tự ghé thăm các thành phố không quan trọng. Thời gian thực hiện các kỳ công không cần phải tính đến.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên $n$ và $m$ ($13 \le n \le 10^5$, $n - 1 \le m \le \min(\frac{n(n-1)}{2}, 10^5)$).

$m$ dòng tiếp theo mô tả các con đường. Dòng thứ $i$ có dạng $a_i$ $b_i$ $c_i$, nghĩa là con đường thứ $i$ kết nối các thành phố có số hiệu $a_i$ và $b_i$, và có độ dài $c_i$ ($1 \le a_i, b_i \le n$, $a_i \neq b_i$, $1 \le c_i \le 1000$). Đảm bảo rằng giữa hai thành phố bất kỳ có tối đa một con đường và có thể đi đến mọi thành phố từ bất kỳ thành phố nào khác.

Mycenae có số hiệu là 1, và các thành phố nơi Heracles phải thực hiện các kỳ công có số hiệu từ 2 đến 13.

Dữ liệu ra

In ra một số nguyên duy nhất — thời gian tối thiểu có thể của chuyến đi.

Ví dụ

Dữ liệu vào 1

15 20
1 2 5
2 3 6
3 4 7
1 14 10
14 5 3
5 6 10
5 7 20
5 8 2
6 7 2
6 8 20
7 8 5
6 9 5
9 11 20
10 9 5
10 11 5
10 15 7
15 12 6
12 13 8
13 14 9
15 4 1000

Dữ liệu ra 1

118

Ghi chú

Một trong những kế hoạch di chuyển tối ưu cho ví dụ trên:

$1 \to 2 \to 3 \to 4 \to 3 \to 2 \to 1 \to 14 \to 5 \to 8 \to 7 \to$ $\to 6 \to 9 \to 10 \to 11 \to 10 \to 15 \to 12 \to 13 \to 14 \to 1$.

Figure 1. Heracles and King Eurystheus