Reliable Nets — Eolymp

Input

There are multiple test cases. Each test case starts with a line containing two integers $n$ ( $n \leq 15$ n \leq 15) and $m$ ( $m \leq 20$ m \leq 20) — the number of buildings (numbered $1$ through $n$ ) and the number of possible connections between buildings. Each of the next $m$ lines contains $b_{1}$ b_1 $b_{2}$ b_2 $c$ (all positive integers), indicating that it costs $c$ to connect building $b_{1}$ b_1 and $b_{2}$ b_2. All connections are bidirectional.

The last test case contains $n = 0$ n = 0 and $m = 0$ m = 0 and is not processed.

Output

For each test case, print one line giving the cost of a minimal reliable net. If such a network exists, the output should be of the form:

The minimal cost for test case $p$ is $c$ .

where $p$ is the test case number (starting from $1$ ), and $c$ is the cost. If there is no reliable net possible, output a line of the form:

There is no reliable net possible for test case $p$ .

Examples

Example 1

Loading