### subroutines

def connected?(n, nbrs, edges)
  used = n.times.map{false}
  used[0] = true
  q = [0]

  while ! q.empty?
    u = q.shift

    for v in nbrs[u]
      if ! edges[u][v].nil? && ! used[v]
        used[v] = true
        q << v
      end
    end
  end

  for usd in used
    return false if ! usd
  end
  true
end

### main

loop do
  n, m = gets.split.map(&:to_i)
  break if n == 0 && m == 0

  min_cost = 0
  nlinks = 0
  links = []
  edges = n.times.map{[]}
  nbrs = n.times.map{[]}

  m.times do
    i, j, w = gets.split.map(&:to_i)
    if w < 0
      min_cost += w
    else
      nlinks += 1
      links << [w, i, j]
      edges[i][j] = edges[j][i] = w
      nbrs[i] << j
      nbrs[j] << i
    end
  end
  links.sort!

  #p links
  #p edges
  #p nbrs

  if nlinks < n - 1 || ! connected?(n, nbrs, edges)
    puts min_cost
    next
  end

  ok = false

  for k in (0...nlinks)
    w, i, j = links[k]
    edges[i][j] = edges[j][i] = nil
    if ! connected?(n, nbrs, edges)
      ok = true
      min_cost += w
      break
    end
    edges[i][j] = edges[j][i] = w
  end

  if ok
    puts min_cost
    next
  end

  links2 = []

  for i in (0...nlinks)
    li = links[i]
    wi = li[0]
    for j in ((i + 1)...nlinks)
      lj = links[j]
      wj = lj[0]
      links2 << [wi + wj, li, lj]
    end
  end

  nlinks2 = links2.length
  links2.sort!
  #p links2

  for k in (0...nlinks2)
    ww, l1, l2 = links[k]
    w1, i1, j1 = l1
    w2, i2, j2 = l2

    edges[i1][j1] = edges[j1][i1] = nil
    edges[i2][j2] = edges[j2][i2] = nil

    if ! connected?(n, nbrs, edges)
      min_cost += ww
      break
    end

    edges[i1][j1] = edges[j1][i1] = w1
    edges[i2][j2] = edges[j2][i2] = w2
  end

  puts min_cost
end