Flow Security
---- --------

You are responsible for getting water from Lake Achu to
the city of Bzurt.  Unfortunately rebels are threatening
to blow up one of the pipes through which the water
flows.   You must estimate the worst amount of damage
they can do.


Input
-----

For each test case, first a line that gives the test
case name.  Then a line of the form

	N P

giving the number N of nodes in the water network and
the number of pipes P connecting them.  Nodes are
numbered 1, 2, ..., N.  After this line there are P
pipe description lines of the form

	n1 n2 f

that state that there is a pipe from node n1 to node n2
with a capacity of f cubic meters per second in either
direction.

Node 1 is Lake Achu and node N is Bzurt.  All numbers
are integers.

    2 <= N <= 10,000
    1 <= P <= 20,000
    1 <= n1, n2 <= N
    n1 != n2
    1 <= f <= 100,000

    sum over all test cases of P * sum f over all pipes
    <= 100,000,000

Input ends with an end of file.  Test case name lines
are at most 80 characters.

Because of the age of the system of pipes, some pipes
are not functional, and these are not listed in the
input.  Because of this, the pipe system may not be
connected, and some nodes may have no pipes into them,
but Lake Achu is always connected to Bzurt.


Output
------

For each test case, first an exact copy of the test case
name line.  Then a line containing just

	F0 F1

where F0 is the maximum flow possible from node 1 to
node N if all pipes are left intact, and F1 is the
smallest maximum flow that will be possible after the
rebels destroy some single pipe.  In other words,
F0 - F1 is the maximum amount the rebels can reduce
the maximum flow of the system by destroying just one
pipe.

All maximum flows are in cubic meters per second.


Sample Input
------ -----

-- SAMPLE 1 --
5 7
1 2 10
2 3 10
3 4 10
4 5 10
1 3 5
2 4 5
3 5 5
-- SAMPLE 2 --
11 15
2 3 8
3 4 8
5 6 6
6 7 6
8 9 4
9 10 4
1 2 3
1 5 2
1 8 4
4 11 4
7 11 3
10 11 2
2 6 5
9 7 5
7 4 3


Sample Output
------ ------

-- SAMPLE 1 --
15 5
-- SAMPLE 2 --
9 5


File:	   flowsecurity.txt
Author:	   Bob Walton <walton@seas.harvard.edu>
Date:	   Sat Oct  6 11:57:26 EDT 2018

The authors have placed this file in the public domain;
they make no warranty and accept no liability for this
file.