We consider a case of a distributed system in which the different parts of the system are connected to each other using peer to peer links. Suppose one of them needs to communicate with the others, and it send a broadcast message. However, in case of a naive implementation, each node forwards any messages it receives to all its neighbors. Thus results in an ever-increasing number of copies of the message being propagated in the network, finally causing it to breakdown when it can no longer handle the load. To address this situation, each node must have a memory so that it ignores previously encountered messages.
Consider a network topology as shown in the above figure. We have 5 nodes, each of which is connected to some of the others using a bidirectional links, each of which has the indicated latency (time it takes between a message being transmitted from one end, and it being received at the other).
Suppose that node A wants to broadcast a message X to all other nodes in the network, and transmits the message to node B at time 0. It reaches node B at time 2, and is then sent to nodes C and D (but not A, as it was the source of the message). It reaches node D at time 3, and is sent to node C and E. At time 4, the message arrives at C from D, but the same message arrives at C from B at time 5. Thus, node C must keep track of all messages that it has received in at least the last 1 time unit so that it knows not to retransmit a previously processed message again.
However, at time 4, C had transmitted copies of the message to nodes B and E, and the one meant for B arrives at time 7. Now, B had last seen the message at time 2, which means in order not to retransmit the message, it must have a memory of at least 5 time units. Finally, two copies of the message reach node E simultaneously from nodes C and D at time 8. In this case, the message from node C is processed first at E (the message from the node with the smaller index is processed first).
Given a network topology and the behavior described above, your task is to calculate the minimum amount of time for which a node must keep in memory previously encountered messages (originating from any node) so that it does not process/forward them again.
- The first line contains the number of test cases T.
- The first line of each testcase contains 2 space-separated integers N (not greater than 100) and E, representing the number of nodes and edges in the network.
- The following E lines (for each testcase) consist of 3 space-separated integers F, T and L, representing an link from node F to node T with latency L.
- F and T are integers in the range 1 to N (inclusive) and L is a non-negative integer not greater than 100.
Output a single integer (on its own line) for each testcase, equal to the minimum memory required by the nodes in the given network so that they do not forward messages already encountered before.
1 2 1
2 3 2
3 1 4
1 2 2
2 3 3
2 4 1
3 4 1
3 5 4
4 5 5
Problem Setter : Kaustubh Karkare