extern crate core;

use std::fmt;
use std::cmp::{Ordering, min, max};
use std::f32::MAX;
use std::ops::{Add, Sub, Mul, Div, Neg, Index, IndexMut, SubAssign, Range};
use std::collections::{BTreeMap, VecDeque, BinaryHeap, BTreeSet, HashMap};
use std::fmt::{Display, Formatter, Error};
use std::hash::{Hash, Hasher};

fn show<T: Display>(vec: &Vec<T>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        print!("[{}", vec[0]);
        for i in 1 .. vec.len() {
            print!(", {}", vec[i]);
        }
        println!("]");
    }
}
fn show2<T: Display>(vec: &Vec<Vec<T>>) {
    if vec.is_empty() {
        println!("[]");
    }else {
        for l in vec {
            show(l);
        }
    }
}
macro_rules! read_line{
    () => {{
        let mut line = String::new();
        std::io::stdin().read_line(&mut line).ok();
        line
    }};
    (delimiter: ' ') => {
        read_line!().split_whitespace().map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (delimiter: $p:expr) => {
        read_line!().split($p).map(|x|x.to_string()).collect::<Vec<_>>()
    };
    (' ') => {
        read_line!(delimiter: ' ')
    };
    ($delimiter:expr) => {
        read_line!(delimiter: $delimiter)
    };
    (' '; $ty:ty) => {
        read_line!().split_whitespace().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
    ($delimiter:expr; $ty:ty) => {
        read_line!($delimiter).into_iter().map(|x|x.parse::<$ty>().ok().unwrap()).collect::<Vec<$ty>>()
    };
}
macro_rules! read_value{
    () => {
        read_line!().trim().parse().ok().unwrap()
    }
}
macro_rules! let_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
macro_rules! let_mut_all {
    ($($n:ident:$t:ty),*) => {
        let line = read_line!(delimiter: ' ');
        let mut iter = line.iter();
        $(let mut $n:$t = iter.next().unwrap().parse().ok().unwrap();)*
    };
}
#[derive(Copy, Clone)]
struct Edge {
    to: usize, pair: usize, flow: i32
}
fn bfs(nodes: &Vec<Vec<Edge>>, source: usize, sink: usize, depth: &mut Vec<i32>) {
    for i in 0 .. depth.len() {
        depth[i] = -1;
    }
    let mut queue = VecDeque::new();
    queue.push_back(source);
    depth[source] = 0;
    while let Some(current) = queue.pop_front() {
        if current == sink {
            break
        }
        for &next in &nodes[current] {
            if next.flow > 0 && depth[next.to] == - 1 {
                depth[next.to] = depth[current] + 1;
                queue.push_back(next.to);
            }
        }
    }
}
fn dfs(nodes: &mut Vec<Vec<Edge>>, current: usize, sink: usize, depth: &Vec<i32>, searching: &mut Vec<usize>, min_flow: i32) -> Option<i32> {
    if current == sink {
        Some(min_flow)
    }else {
        while searching[current] < nodes[current].len() {
            let Edge{to: next, pair: pair, flow: flow} = nodes[current][searching[current]];
            if flow > 0 && depth[current] < depth[next] {
                if let Some(pushed_flow) = dfs(nodes, next, sink, depth, searching, min(min_flow, flow)) {
                    nodes[current][searching[current]].flow -= pushed_flow;
                    nodes[next][pair].flow += pushed_flow;
                    return Some(pushed_flow)
                }
            }
            searching[current] += 1;
        }
        None
    }
}
fn cal_max_flow(nodes: &mut Vec<Vec<Edge>>, source: usize, sink: usize) -> i64 {
    let mut depth = vec![-1; nodes.len()];
    let mut searching = vec![0; nodes.len()];
    let mut sum_flow = 0_i64;
    let mut has_flow = true;
    while has_flow {
        has_flow = false;
        bfs(nodes, source, sink, &mut depth);
        for i in 0 .. searching.len() {
            searching[i] = 0;
        }
        while let Some(flow) = dfs(nodes, source, sink, &depth, &mut searching, std::i32::MAX) {
            has_flow = true;
            sum_flow += flow as i64;
        }
    }
    sum_flow
}
fn make_flow_network(size: usize, graph: &Vec<(usize, usize, i32)>) -> Vec<Vec<Edge>> {
    let mut result = vec![Vec::new(); size];
    for &(a, b, c) in graph {
        let len_a = result[a].len();
        let len_b = result[b].len();
        result[a].push(Edge{to: b, pair: len_b, flow: c});
        result[b].push(Edge{to: a, pair: len_a, flow: c});
    }
    result
}
fn reset_flow_network(nodes: &mut Vec<Vec<Edge>>) {
    for i in 0 .. nodes.len() {
        for j in 0 .. nodes[i].len() {
            let e = nodes[i][j];
            if e.to > i {
                let flow = (e.flow + nodes[e.to][e.pair].flow) / 2;
                nodes[i][j].flow = flow;
                nodes[e.to][e.pair].flow = flow;
            }
        }
    }
}
fn cal_min_cost(size: usize, edges: Vec<(usize, usize, i32)>) -> i64 {
    let mut network = make_flow_network(size, &edges);
    let mut min_cost = std::i64::MAX;
    for i in 1 .. size {
        let cost = cal_max_flow(&mut network, 0, i);
        if cost < min_cost {
            min_cost = cost;
        }
        reset_flow_network(&mut network);
    }
    min_cost
}
fn main() {
    loop {
        let_all!(n: usize, m: usize);
        if n == 0 && m == 0 {
            return
        }
        let mut default_cost = 0_i64;
        let mut edges = Vec::with_capacity(m);
        for _ in 0 .. m {
            let_all!(x: usize, y: usize, c: i32);
            if c > 0 {
                edges.push((x, y, c));
            }else {
                default_cost += c as i64;
            }
        }
        println!("{}", cal_min_cost(n, edges) + default_cost);
    }
}



Measured memory_bytes: 5052