Median Tree — Eolymp

Input

The input consists of multiple datasets.

The format of each dataset is as follows:

$n m$

$s_{1} t_{1} c_{1}$ s_1\ t_1\ c_1

$\dots$

$s_{m} t_{m} c_{m}$ s_m\ t_m\ c_m

The first line contains an even number $n$ ( $2 \leq n \leq 1000$ 2 \leq n \leq 1000) and an integer $m$ ( $n - 1 \leq m \leq 10000$ n-1 \leq m \leq 10000). $n$ is the number of nodes and $m$ is the number of edges in the graph.

Then $m$ lines follow, each of which contains $s_{i}$ s_i ( $1 \leq s_{i} \leq n$ 1 \leq s_i \leq n), $t_{i}$ t_i ( $1 \leq t_{i} \leq n$ 1 \leq t_i \leq n, $t_{i} \neq = s_{i}$ t_i \neq s_i), and $c_{i}$ c_i ( $1 \leq c_{i} \leq 1000$ 1 \leq c_i \leq 1000).

This means there is an edge between nodes $s_{i}$ s_i and $t_{i}$ t_i, and its cost is $c_{i}$ c_i. There is no more than one edge that connects $s_{i}$ s_i and $t_{i}$ t_i.

The input terminates when $n = 0$ n = 0 and $m = 0$ m = 0. Your program must not output anything for this case.

Output

Print the median value in a line for each dataset.

Examples

Example 1

Loading