In computer networks, the Internet Protocol (IP) uses path routing. With path routing, the packet contains only the destination address; routers decide which “next hop” to forward each packet on to get it closer to its destination. Each router makes this decision locally, based only on the destination address and its local configuration. One way to store this configuration is to use routing tables, which means for each router, we store the “next hop” for every possible destination. However, as the scale of the network grows larger, the size of the router table grows as well. It is a big issue since routers only have limited computing resources. One way to address this issue is to divide the graph into several partitions.

## [Solution] Optimal Graph Partition for Fast Routing solution codeforces

## [Solution] Optimal Graph Partition for Fast Routing solution codeforces

A computer network under consideration is an undirected connected graph 𝐺=(𝑉,𝐸)G=(V,E), where |𝑉|=𝑁 (2≤𝑁≤105)|V|=N (2≤N≤105), |𝐸|=𝑀 (1≤𝑀≤2×105)|E|=M (1≤M≤2×105), 𝑉={0,1,…,𝑁−1}V={0,1,…,N−1}, 𝐸={𝑒=(𝑢,𝑣,𝑤)∣There is an edge between nodes 𝑢 and 𝑣 with weight 𝑤}.E={e=(u,v,w)∣

There is an edge between nodes u and v with weight w}.

A partition 𝑃P of the network 𝐺G is a set of non-empty subsets of 𝑉V such that every node 𝑣∈𝑉v∈V belongs to exactly one of these subsets, and the induced sub-graph for each subset in 𝑃P is connected. Here, one subset corresponds to one abstract node mentioned above.

Formally, 𝑃P is a valid partition if and only if 𝑃P is a family of sets that satisfies:

- ∅∉𝑃∅∉P
- ⋃𝐴∈𝑃𝐴=𝑉⋃A∈PA=V
- ∀𝐴,𝐵∈𝑃:𝐴≠𝐵⟹𝐴∩𝐵=∅∀A,B∈P:A≠B⟹A∩B=∅
- ∀𝐴∈𝑃∀A∈P, the induced subgraph 𝐺[𝐴]G[A] is connectedThe set

𝐹𝐸(𝑃)FE(P) of free edges of the partition 𝑃P are those edges that are not part of the merged nodes, that is, those edges that connect the merged nodes. 𝑤(𝑒)w(e) is the weight of the edge 𝑒e.

In this subtask, it is necessary to solve a narrowed bi-criteria optimization problem:The score for SubTask1 for the

𝑖𝑡ℎith graph is calculated by the formula:

Input

## [Solution] Optimal Graph Partition for Fast Routing solution codeforces

The first line contains two integers 𝑁N and 𝑀M (2≤𝑁≤105;𝑁−1≤𝑀≤2×105)(2≤N≤105;N−1≤M≤2×105) — the number of nodes and edges, respectively.

Each of the next 𝑀M lines contains three integers 𝑢𝑖,𝑣𝑖ui,vi and 𝑤𝑖wi (0≤𝑢𝑖, 𝑣𝑖≤𝑁−1, 𝑢𝑖≠𝑣𝑖, 1≤𝑤𝑖≤1050≤ui, vi≤N−1, ui≠vi, 1≤wi≤105), denoting an edge between the node 𝑢𝑖ui and 𝑣𝑖vi with weight 𝑤𝑖wi. 𝑒𝑖=(𝑢𝑖,𝑣𝑖,𝑤𝑖)ei=(ui,vi,wi) is the edge with index 𝑖i in the edge set 𝐸E. It is guaranteed that the input graph is connected and there are no multiple edges. That is, any pair (in any order) of nodes appear in this list no more than once.

In the first line, output the number of subsets in your partition 𝑃P.

The (𝑖+1)(i+1)-th line should begin with a single number 𝑐𝑛𝑡𝑖cnti — the size of the 𝑖i-th subset, followed by 𝑐𝑛𝑡𝑖cnti numbers, denoting the node IDs in the 𝑖i-th subset.

## [Solution] Optimal Graph Partition for Fast Routing solution codeforces

Scoring

During the coding phase, your solutions are tested against pre-tests only. The first 55 of them are open and available for download at the link problem-gp1-open-testset.zip in the “contest materials” section in a sidebar.

After the end of the coding phase, the last submission that scored a positive number of points on the pre-tests will be selected. It will be retested in the final tests. The rest of your submissions will be ignored. The final tests are secret and not available to the participants, they are mostly realistic. The result obtained on the final tests is your final official result for this problem.

- According to the formula, the solution with a larger score wins.
- If two solutions have the same score, the solution submitted first wins.