The phone rings at Chris's house, and his teacher's anxious voice comes through: "Hello, is this Chris's parent? Your child is absent from class again. Does he not want to take the exam?" Upon hearing about the exam, Chris's parents are frantic and decide to find Chris as quickly as possible. They tell Chris's teacher: "Based on our past experience, Chris must be hiding at his friend Shermie's or Yashiro's house playing The King of Fighters. We are leaving home now to find him, and we will call you as soon as we do." With that, they hang up the phone with a bang.

The city where Chris lives consists of $N$ residential points and several bidirectional streets connecting them. Traveling through a street takes $T_x$ minutes. It is guaranteed that there is exactly one path between any two residential points. Chris's home is at point $C$, and Shermie and Yashiro live at points $A$ and $B$, respectively. Both Chris's teacher and his parents have a map of the city, but while Chris's parents know the specific locations of $A$, $B$, and $C$, the teacher does not. To find Chris as quickly as possible, Chris's parents follow these two rules:

• If the distance from $A$ to $C$ is shorter than the distance from $B$ to $C$, Chris's parents will first go to Shermie's house to look for Chris; if they cannot find him, they will then go to Yashiro's house. The same logic applies in reverse.
• Chris's parents always travel along the unique path between two points.

Clearly, Chris's teacher knows that Chris's parents will follow these two rules while searching for him, but since he does not know the specific locations of $A$, $B$, and $C$, he wants you to tell him: in the worst-case scenario, how much time will it take for Chris's parents to find him?

As shown in the figure above, the city consists of 4 residential points and 3 streets, and it takes 1 minute to travel through each street. Suppose Chris lives at point $C$, Shermie lives at point $A$, and Yashiro lives at point $B$. Since the distance from $C$ to $B$ is less than the distance from $C$ to $A$, Chris's parents will first go to Yashiro's house to look for Chris, and if they do not find him, they will go to Shermie's house. Thus, in the worst-case scenario, it will take Chris's parents 4 minutes to find him.

Input

The first line contains two integers $N$ ($3 \le N \le 200000$) and $M$, representing the total number of residential points and the total number of streets. The following $M$ lines each provide information about a street. The $(i+1)$-th line contains integers $U_i$, $V_i$, and $T_i$ ($1 \le U_i, V_i \le N$, $1 \le T_i \le 1000000000$), indicating that street $i$ connects residential points $U_i$ and $V_i$, and it takes $T_i$ minutes to travel through it. Street information will not be repeated.

Output

Output a single integer $T$, representing the time in minutes it takes for Chris's parents to find him in the worst-case scenario.

Examples

Input 1

4 3 
1 2 1 
2 3 1 
3 4 1

Output 1

4