{"raw_statement":[{"iden":"problem statement","content":"There is a simple connected undirected graph with $N$ vertices numbered $1$ to $N$. The graph has $M$ weighted edges, and the $i$\\-th edge connects vertices $A_i$ and $B_i$ with a weight of $W_i$. Additionally, let the weight of a simple path connecting two vertices be the sum of the weights of the edges contained in the simple path.\nLet us paint each vertex red or blue. Find the maximum value of the integer $X$ for which there is a coloring that satisfies the following condition:\n\n*   For every simple path connecting two different vertices painted in the same color, the weight of the simple path is at least $X$.\n\nWhat is a simple path? For vertices $X$ and $Y$ in a graph $G$, a sequence of vertices $v_1,v_2, \\ldots, v_k$ such that $v_1=X$, $v_k=Y$, and $v_i$ and $v_{i+1}$ are connected by an edge for each $1\\leq i\\leq k-1$ is called a **walk** from vertex $X$ to vertex $Y$. Furthermore, if $v_1,v_2, \\ldots, v_k$ are all different, the walk is called a **simple path** (or just **path**)."},{"iden":"constraints","content":"*   $3 \\leq N \\leq 2 \\times 10^5$\n*   $N-1 \\leq M \\leq \\min(\\frac{N(N-1)}{2},2 \\times 10^5)$\n*   $1 \\leq A_i < B_i \\leq N$\n*   $1 \\leq W_i \\leq 10^9$\n*   The given graph is a simple connected undirected graph.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $W_1$\n$A_2$ $B_2$ $W_2$\n$\\vdots$\n$A_M$ $B_M$ $W_M$"},{"iden":"sample input 1","content":"3 3\n1 2 5\n2 3 6\n1 3 12"},{"iden":"sample output 1","content":"11\n\nConsider whether there is a coloring that satisfies the condition for $X=11$. If we paint vertices $1$ and $3$ red and vertex $2$ blue, the simple path $1-2-3$ connecting vertices of the same color has a weight of $5+6=11$. This is the minimum weight of a simple path connecting vertices of the same color, so this coloring satisfies the condition.\nIt can be shown that no coloring satisfies the condition for $X=12$ or above. Thus, the answer is $11$."},{"iden":"sample input 2","content":"10 20\n7 10 982219000\n3 10 968366179\n2 4 992330437\n5 6 984414664\n2 8 897295423\n7 9 155604979\n6 8 958833005\n2 3 973209957\n3 7 985173062\n6 10 963895817\n2 10 986243534\n4 5 721724794\n1 3 657562445\n1 6 566370694\n1 4 988050146\n1 9 967817807\n4 9 796531581\n5 9 983960054\n1 10 964450079\n8 9 959369491"},{"iden":"sample output 2","content":"952136560"},{"iden":"sample input 3","content":"10 20\n5 6 871895994\n8 10 873709822\n3 5 454175869\n6 10 980782191\n2 6 901290987\n1 8 298092290\n4 8 693116157\n4 5 947939338\n7 8 934395075\n7 9 759563833\n5 8 779870031\n4 6 919637355\n2 9 822858749\n4 10 855497285\n3 7 954942051\n1 2 950411658\n4 7 665939990\n3 4 634533617\n5 7 908372507\n1 9 591466693"},{"iden":"sample output 3","content":"759563833"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}