N,M = map(int,input().split())
soronkent = list(map(int,input().split()))

matrix = []
for Oszlop in range(M):
    sor = list(map(int,input().split()))
    matrix.append(sor)

if N == 2:
    #Mindkét sor festve
    eset = [sum(soronkent)]
    #Csak első sor festve
    osszeg = soronkent[0]
    for Oszlop in range(M):
        osszeg += min([matrix[Oszlop][2],matrix[Oszlop][1]])
    eset.append(osszeg)
    #Csak második sor festve
    osszeg = soronkent[1]
    for Oszlop in range(M):
        osszeg += min([matrix[Oszlop][0],matrix[Oszlop][1]])
    eset.append(osszeg)
    #Nincs sor festve
    osszeg = 0
    for Oszlop in range(N):
        osszeg += min([matrix[Oszlop][0]+matrix[Oszlop][2],matrix[Oszlop][1]])
    eset.append(osszeg)
    print(min(eset))
if N == 3:
                                
    print(100)
if N == 4:
                           
    print(100)