Tengo una matriz 2d en Python llamada "AllLines"

[['Suppliers', 'Spend', 'Test Field\n'], 
 ['Dell Inc', '9000', '1\n'], 
 ['Dell Computers', '9000', '2\n'], 
 ['HBC Corp', '9000', '3\n'], 
 ['HBC INC', '9000', '4']]

Por lo tanto, es una matriz dentro de una matriz. Necesito añadir elementos a la matriz interna. Para darme esto:

[['NEW','Suppliers', 'Spend', 'Test Field\n'], 
 ['N-E-W','Dell Inc', '9000', '1\n'], 
 ['N-E-W---','Dell Computers', '9000', '2\n'], 
 ['N-E---W','HBC Corp', '9000', '3\n'], 
 ['N-W-W','HBC INC', '9000', '4']]

¿Cómo logro agregar un nuevo elemento a las matrices internas?