local function uf_initialize(n)
  local parent = {}
  for i = 1, n do parent[i] = i end
  return parent
end

local function uf_findroot(idx, parent)
  local idx_update = idx
  while parent[idx] ~= idx do
    idx = parent[idx]
  end
  while parent[idx_update] ~= idx do
    parent[idx_update], idx_update = idx, parent[idx_update]
  end
  return idx
end

local n = io.read("*n")
local edge = {}
for i = 1, n do
  for j = 1, n do
    local c = io.read("*n")
    if i < j then
      local tmp = {}
      tmp.c, tmp.i1, tmp.i2 = c, i, j
      table.insert(edge, tmp)
    end
  end
end

local e = {}
for i = 1, n do e[i] = {} end

local function getlen(start_idx, dst_idx)
  local taskstate = {}
  for i = 1, n do taskstate[i] = false end
  local tasks = {}
  local tasknum = 0
  local done = 0

  local len = {}
  for i = 1, n do len[i] = 300000000000 end
  len[start_idx] = 0

  local function addtask(idx)
    if not taskstate[idx] then
      taskstate[idx] = true
      tasknum = tasknum + 1
      tasks[tasknum] = idx
    end
  end
  addtask(start_idx)

  while done < tasknum do
    done = done + 1
    local src = tasks[done]
    taskstate[src] = false
    for dst, cost in pairs(e[src]) do
      if len[src] + cost < len[dst] then
        len[dst] = len[src] + cost
        addtask(dst)
      end
    end
  end
  return len[dst_idx]
end

table.sort(edge, function(a, b) return a.c < b.c end)
local parent = uf_initialize(n)
local totalcost = 0
local flg = true
local linenum = #edge
for i = 1, linenum do
  local c, i1, i2 = edge[i].c, edge[i].i1, edge[i].i2
  local r1, r2 = uf_findroot(i1, parent), uf_findroot(i2, parent)
  parent[i1], parent[i2] = r1, r2
  if r1 ~= r2 then
    parent[r2] = r1
    parent[i2] = r1
    totalcost = totalcost + c
  else
    local len = getlen(i1, i2)
    if c < len then
      totalcost = totalcost + c
    elseif len < c then
      flg = false
    end
  end
  e[i1][i2], e[i2][i1] = c, c
end
print(flg and totalcost or -1)
