package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

const NEG int = -1 << 60

type FastScanner struct {
	data []byte
	idx  int
	n    int
}

func NewFastScanner() *FastScanner {
	data, _ := io.ReadAll(os.Stdin)
	return &FastScanner{data: data, n: len(data)}
}

func (fs *FastScanner) NextInt() int {
	for fs.idx < fs.n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	val := 0
	for fs.idx < fs.n {
		c := fs.data[fs.idx]
		if c < '0' || c > '9' {
			break
		}
		val = val*10 + int(c-'0')
		fs.idx++
	}
	return sign * val
}

func identity(n int) []int {
	a := make([]int, n*n)
	for i := range a {
		a[i] = NEG
	}
	for i := 0; i < n; i++ {
		a[i*n+i] = 0
	}
	return a
}

func mul(a, b []int, n int) []int {
	c := make([]int, n*n)
	for i := range c {
		c[i] = NEG
	}
	for i := 0; i < n; i++ {
		ai := i * n
		ci := c[ai : ai+n]
		for k := 0; k < n; k++ {
			av := a[ai+k]
			if av == NEG {
				continue
			}
			bk := k * n
			for j := 0; j < n; j++ {
				bv := b[bk+j]
				if bv == NEG {
					continue
				}
				v := av + bv
				if v > ci[j] {
					ci[j] = v
				}
			}
		}
	}
	return c
}

func hasPositiveDiag(a []int, n int) bool {
	for i := 0; i < n; i++ {
		if a[i*n+i] > 0 {
			return true
		}
	}
	return false
}

func main() {
	fs := NewFastScanner()
	n := fs.NextInt()
	m := fs.NextInt()

	base := identity(n)
	found2 := false

	for t := 0; t < m; t++ {
		i := fs.NextInt() - 1
		j := fs.NextInt() - 1
		cij := fs.NextInt()
		cji := fs.NextInt()
		base[i*n+j] = cij
		base[j*n+i] = cji
		if cij+cji > 0 {
			found2 = true
		}
	}

	out := bufio.NewWriterSize(os.Stdout, 64)
	defer out.Flush()

	if found2 {
		out.WriteString("2\n")
		return
	}

	pows := make([][]int, 0, 10)
	pows = append(pows, base)
	for size := 1; size*2 <= n; size *= 2 {
		pows = append(pows, mul(pows[len(pows)-1], pows[len(pows)-1], n))
	}

	cur := identity(n)
	lenNo := 0

	for b := len(pows) - 1; b >= 0; b-- {
		step := 1 << uint(b)
		if lenNo+step > n {
			continue
		}
		var cand []int
		if lenNo == 0 {
			cand = pows[b]
		} else {
			cand = mul(cur, pows[b], n)
		}
		if !hasPositiveDiag(cand, n) {
			lenNo += step
			cur = cand
		}
	}

	ans := 0
	if lenNo < n {
		ans = lenNo + 1
	}
	out.WriteString(strconv.Itoa(ans))
	out.WriteByte('\n')
}