import scala.collection.mutable

object Main extends App {

  import scala.io.StdIn._
  import scala.math._
  val Array(v, e) = readLine.trim.split(' ').map(_.toInt)
  val edges = Array.tabulate(v){_ ⇒ mutable.Map[Int, Int]()}
  var singleEdge: List[(Int, Int)] = Nil
  for (_ ← 0 until e){
    val Array(s, t, c) = readLine.trim.split(' ').map(_.toInt)
    edges(s)(t) = c
    edges(t)(s) = c
    if (c == 1){
      singleEdge ::= (s, t)
    }
  }
  val maxFlow = calFlow(edges, 0, v - 1)


  println(
    canReachAll(edges, singleEdge) match {
      case false ⇒
        val flow = maxFlow - 1
        if (flow > 10000) -1
        else flow
      case true ⇒
        if (maxFlow > 10000) - 1
        else maxFlow
    }
  )
  def canReachAll(nodes: Array[mutable.Map[Int, Int]], pairs: List[(Int, Int)]): Boolean = {
    implicit val isSearched = Array.tabulate(nodes.length){_ ⇒ false}
    def canReach(nodes: Array[mutable.Map[Int, Int]], start: Int, goal: Int)(implicit isSearched: Array[Boolean]): Boolean = {
      val queue: mutable.Queue[Int] = mutable.Queue()
      queue.enqueue(start)
      isSearched(start) = true
      var isReachable = false
      while (queue.nonEmpty && !isReachable){
        val from = queue.dequeue()
        for ((to, _) ← nodes(from)){
          if (!isSearched(to)){
            isSearched(to) = true
            queue.enqueue(to)
            if (goal == to) isReachable = true
          }
        }
      }
      isSearched.indices.foreach(i ⇒ isSearched(i) = false)
      isReachable
    }
    pairs.forall{
      case (f, t) ⇒ canReach(nodes, f, t) && canReach(nodes, t, f)
    }
  }
  def calFlow(nodes:Array[mutable.Map[Int, Int]], start: Int, goal: Int): Long = {
    val queue: mutable.Queue[Int] = mutable.Queue()
    val prev = Array.tabulate(nodes.length){_ ⇒ -1}
    var isReached: Boolean = true
    var result = 0L
    while (isReached) {
      isReached = false
      queue.enqueue(start)
      while (queue.nonEmpty && !isReached) {
        val from = queue.dequeue()
        for ((to, _) ← nodes(from) if !isReached){
          if (prev(to) == -1 && to != start){
            prev(to) = from
            queue.enqueue(to)
            if (to == goal) isReached = true
          }
        }
      }
      if (isReached){
        queue.clear()
        var to = goal
        var from = prev(goal)
        var minFlow = Int.MaxValue
        while (from != -1){
          minFlow = math.min(minFlow, nodes(from)(to))
          to = from
          from = prev(from)
        }
        to = goal
        from = prev(goal)
        while(from != -1){
          if (nodes(from)(to) == minFlow){
            nodes(from).remove(to)
          }else {
            nodes(from)(to) = nodes(from)(to) - minFlow
          }
          if (nodes(to).contains(from)){
            nodes(to)(from) = nodes(to)(from) + minFlow
          }else{
            nodes(to).put(from, minFlow)
          }
          to = from
          from = prev(from)
        }
        result += minFlow
        prev.indices.foreach(i ⇒ prev(i) = -1)
      }
    }
    result
  }


  implicit class Extension[T](val value :T){
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
    def let[R](func: T ⇒ R): R = func(value)
  }
}


Measured memory_bytes: 449336