P1340 Beast Trail Management

The herd on Farmer John's farm wants to be able to move freely among $N$ pastures labeled $1$ to $N$, which are separated by forests. They wish to choose routes between pastures so that the herd can travel from any pasture to any other pasture. The herd can travel in both directions along a route. The herd cannot create new routes, but they will keep and use trails made by wild animals (hereafter called "game trails"). Each week, they choose and manage some or all of the known game trails as usable routes. At the start of each week, the herd discovers one new game trail. They must then decide which game trails to manage for that week to form their network of routes, so that the herd can travel from any pasture to any other pasture. The herd may only use the trails that are managed during that week. They want the sum of lengths of the managed trails to be as small as possible. They may choose any subset of all game trails they have discovered so far. Whether a trail was managed in a previous week does not matter. Game trails are never straight lines, so different trails connecting the same pair of pastures may have different lengths. Although two game trails may intersect, the herd is very focused and will not switch trails at intersections unless the intersection lies inside a pasture. At the beginning of each week, the herd will describe the newly discovered game trail. If possible, find a set of managed game trails that makes all pastures mutually reachable, with the minimum possible total length.

The first line contains two integers $N$ and $W$ separated by a space. $W$ is the number of weeks your program needs to process. For each subsequent week, read one line describing the newly discovered game trail. The line contains three integers separated by spaces: the two endpoints of the trail (the pasture labels) and the trail’s length. The two endpoints of a game trail are always distinct.

After reading each newly discovered game trail, immediately output the minimum possible total length of a set of trails that makes all pastures mutually reachable. If no such set exists, output $-1$. Output one result per week on its own line.

### Sample Explanation For each week: - In week 1, pasture $4$ cannot connect to the others, so output $-1$. - In week 2, pasture $4$ cannot connect to the others, so output $-1$. - In week 3, pasture $4$ cannot connect to the others, so output $-1$. - In week 4, you can choose trails $(1, 4, 3)$, $(1, 3, 8)$, and $(3, 2, 3)$. - In week 5, you can choose trails $(1, 4, 3)$, $(1, 3, 6)$, and $(3, 2, 3)$. - In week 6, you can choose trails $(1, 4, 3)$, $(2, 1, 2)$, and $(3, 2, 3)$. ### Constraints For all testdata, $1 \le N \le 200$, $1 \le W \le 6000$, and each trail length is a positive integer not exceeding $10^4$. Translated by ChatGPT 5