OIT needs your help. eduroam is having some problems 1 and the network engineers at OIT want you to help them figure out if their current network configuration has enough bandwidth to send data from a particular source to a specific destination. If not, then they can add some more NSA wireless routers to give a better user experience 2. Otherwise, they can blame it on nargles.

For instance, given the network on the right, we have four nodes and five connections with varying bandwidth capacities. For instance, node 1 and 2 have a bandwidth of 20 and node 3 and node 1 have a bandwidth of 10. The total maximum bandwidth between the source (1) and the destination (4) is 25. This is because we can send bandwidth 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4, for a total of 25.

Your mission is to write a program that computes the maximum bandwidth between two given nodes in a network. For this problem, you can assume that the bandwidth of a connection is always the same in both directions (which is not necessarily true in the real world).

Input

You will be given a series of networks. The first line of the input specifies the number of nodes in the network (2 <= n <= 100). This is followed by a line that contains the source, target, and total number of connections. After this, you will be given the specification for each connection in the form of node 1, node 2, and capacity.

The final network will specify 0 nodes and should not be displayed.

Note: All connections are bi-directional, and there may be multiple connections between a pair of nodes (but a node cannot connect to itself).

Example Input

This is the sample input that corresponds to the image above:

4
1 4 5
1 2 20
1 3 10
2 3 5
2 4 10
3 4 20
0

Output

For each network configuration, print the network number (starting with 1) and the maximum bandwidth as shown below.

Example Output

Network 1: Bandwidth is 25.

Algorithmic Complexity

For each input test case, your solution should have the following targets:

Time Complexity O(VE^2), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity O(V+E), where V is the number of vertices and E is the number of edges in the graph.

Your solution may be below the targets, but it should not exceed them.

Programming Challanges

This is based on 820 - Internet Bandwidth problem on the UVa Online Judge.

Submission

To submit your work, follow the same procedure you used for [Reading 00]:

$ cd path/to/cse-30872-fa22-assignments     # Go to assignments repository
$ git checkout master                       # Make sure we are on master
$ git pull --rebase                         # Pull any changes from GitHub

$ git checkout -b challenge21               # Create and checkout challenge21 branch

$ $EDITOR challenge21/program.py            # Edit your code

$ git add challenge21/program.py            # Stage your changes
$ git commit -m "challenge21: done"         # Commit your changes

$ git push -u origin challenge21            # Send changes to GitHub

To check your code, you can use the .scripts/check.py script or curl:

$ .scripts/check.py
Checking challenge21 program.py ...
  Result Success
    Time 0.06
   Score 6.00 / 6.00

$ curl -F source=@challenge21/program.cpp https://dredd.h4x0r.space/code/cse-30872-fa22/challenge21
{"result": "Success", "score": 6, "time": 0.06403017044067383, "value": 6, "status": 0}

Pull Request

Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the instructor.


  1. Quelle surprise. 

  2. We can only wish.