text: # Problem Problem A large-scale cluster † type supercomputer (commonly known as "SAKURA") cluster at Maze University consists of $ N $ computers (nodes) and $ M $ physical communication channels that can communicate with each other...In addition, each node is assigned an identification number from 1 to $ N $.This time, the use of SAKURA will be approved not only by university personnel but also by companies in the prefecture.Along with that, it is necessary to inspect each node that composes SAKURA.However, since the usage schedule of SAKURA is filled up to several months ahead, the entire system cannot be stopped even during the inspection.Therefore, inspect the nodes one by one a day.The inspection takes place over $ N $ days and inspects the node $ i $ on the $ i $ day.At this time, the node to be inspected and the communication path directly connected to that node are separated from the SAKURA cluster.As a result, the entire cluster of SAKURA is divided into one or more clusters, and one of them is operated in place of SAKURA.Naturally, the node under inspection cannot be operated.When divided into multiple clusters, only the cluster with the highest "overall performance value" is operated.The "total performance value" of each cluster is the sum of the "single performance values" set for each node that composes it.Since the number of nodes that make up SAKURA, the number of communication channels, and the "single performance value" set for each node are given, the "total performance value" of the cluster operated during the inspection on the $ i $ day is output.Let's do it.†: A cluster is a system that combines one or more computers into a single unit.Here, it is a set of nodes connected by a physical communication path.Constraints The input satisfies the following conditions.