Balancing Art

Pete Tencious is a world-renowned artist who specializes in mobiles. The San Francisco Museum of Art is displaying a collection of his artwork called Balance I, Balance II, Balance III, and so on. Each work has two or more spheres with wires strung between them. Disks hang at the ends of each wire and attach to the two spheres that the wire connects. If you sum the disks at each sphere, you get the same number every time. Pete calls this the balance number of the mobile. Some wires also have extra disks suspended between spheres. The artist says this represents the balance of nature (the disks on the spheres) corrupted by humankind (the extra disks between the spheres).

An earthquake in the Bay Area has dislodged the disks, and now they all hang loose between spheres. Pete is working on Balance CCXLI and cannot be reached, so the museum curators must fix the mobiles themselves. They do not remember the balance number for each mobile. They decide it should be as large as possible, and they want as few disks as possible left hanging between the spheres. Figure C.1 shows one mobile after the earthquake, matching the first sample. Figure C.2 shows one way the curators could move the disks so that every sphere has the same number of disks while leaving the fewest disks between the spheres.

Figure C.1: After the earthquake

Figure C.2: Disks moved to maximize the balance number

The first line contains two positive integers $n$ and $m$, where $n$ ($2 \leq n \leq 200$) is the number of spheres, numbered 1 to $n$, and $m$ ($1 \leq m \leq 500$) is the number of wires. Each of the next $m$ lines has three integers $s_1$, $s_2$, and $d$, where $s_1$ and $s_2$ ($1 \leq s_1, s_2 \leq n$, $s_1 \neq s_2$) are the two spheres connected by a wire, and $d$ ($0 \leq d \leq 10\,000$) is the number of disks hanging on that wire after the earthquake. There is at most one wire between any two spheres.

Output the minimum number of disks left hanging on the wires between spheres after the balance number is maximized.