import java.util.*

data class Line(val to: Int, val firstTime: Int, val secondTime: Int)
fun minFrom(startA: Int, startB: Int, path: Array<out Collection<Line>>, hasPath: Array<Array<Boolean>>, memo: Array<Array<Int?>>): Int {
    if (memo[startA][startB] == null){
        memo[startA][startB] = when {
            startA == startB -> {
                path[startA].mapNotNull { nextA ->
                    path[startB].map { nextB ->
                        if (nextA == nextB) minFrom(nextA.to, nextB.to, path, hasPath, memo) + nextA.firstTime + nextA.secondTime
                        else minFrom(nextA.to, nextB.to, path, hasPath, memo) + nextA.firstTime + nextB.firstTime
                    }.min()
                }.min() ?: 0
            }
            hasPath[startA][startB] -> {
                path[startA].map { next -> minFrom(next.to, startB, path, hasPath, memo) + next.firstTime }.min()!!
            }
            else -> {
                path[startB].map { next -> minFrom(startA, next.to, path, hasPath, memo) + next.firstTime }.min()!!
            }
        }
    }
    return memo[startA][startB]!!
}
fun hasPath(from: Int, to: Int, path: Array<out Collection<Line>>, memo: Array<Array<Boolean?>>): Boolean {
    if (memo[from][to] == null){
        memo[from][to] = from == to || path[from].any{next -> hasPath(next.to, to, path, memo)}
    }
    return memo[from][to]!!
}
fun main(args:Array<String>?): Unit {
    val (n, p) = readLine()!!.trim().split(' ').map(String::toInt)
    val flags = Array(n){ Stack<Line>() }
    repeat(p){
        val (s, e, t1, t2) = readLine()!!.trim().split(' ').map(String::toInt)
        flags[s - 1].push(Line(e - 1, t1, t2))
    }
    val path = Array(n){Array<Boolean?>(n){null}}.let{memo ->
        for (i in 0 until n) for (j in 0 until n){
            hasPath(i, j, flags, memo)
        }
        memo.map{it.filterNotNull().toTypedArray()}.toTypedArray()
    }
    val memo = Array(n){f -> Array(n){t -> if (f == n - 1 && t == n - 1) 0 else null}}
    println(
            minFrom(0, 0, flags, path, memo)
    )
}
