{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"![Netowrk Traffic](CDN_BASE_URL/5d08ad926ce04542b97b08763f073ada?v\u003d1715666600)\n\nOn the Internet, machines (nodes) are richly interconnected, and many paths may exist between a given pair of nodes. The total message-carrying capacity (bandwidth) between two given nodes is the maximal amount of data per unit time that can be transmitted from one node to the other. Using a technique called packet switching; this data can be transmitted along several paths at the same time.\n\nFor example, the figure shows a network with four nodes (shown as circles), with a total of five connections among them. Every connection is labeled with a bandwidth that represents its data-carrying capacity per unit time.\n\nIn our example, the bandwidth between node 1 and node 4 is 25, which might be thought of as the sum of the bandwidths 10 along the path 1-2-4, 10 along the path 1-3-4, and 5 along the path 1-2-3-4. No other combination of paths between nodes 1 and 4 provides a larger bandwidth.\n\nYou must write a program that computes the bandwidth between two given nodes in a network, given the individual bandwidths of all the connections in the network. In this problem, assume that the bandwidth of a connection is always the same in both directions (which is not necessarily true in the real world)."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 30)**, denoting the number of test cases.\n\nEvery description starts with a line containing an integer **n (2 \u0026le; n \u0026le; 100)**, which is the number of nodes in the network. The nodes are numbered from **1** to **n**. The next line contains three numbers **s**, **t**, and **c**. The numbers **s** and **t** are the source and destination nodes, and the number **c (c \u0026le; 5000, s \u0026ne; t)** is the total number of connections in the network. Following this are **c** lines describing the connections. Each of these lines contains three integers: the first two are the numbers of the connected nodes, and the third number is the bandwidth of the connection. The bandwidth is a non-negative number not greater than **1000**.\n\nThere might be more than one connection between a pair of nodes, but a node cannot be connected to itself. All connections are bi-directional, i.e. data can be transmitted in both directions along a connection, but the sum of the amount of data transmitted in both directions must be less than the bandwidth."}},{"title":"Output","value":{"format":"MD","content":"For each case of input, print the case number and the total bandwidth between the source node **s** and the destination node **t**."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n1 4 5\n1 2 20\n1 3 10\n2 3 5\n2 4 10\n3 4 20\n4\n1 4 2\n1 4 20\n1 4 20\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 25\nCase 2: 40\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}