In spatial statistics, the estimation of covariance matrices is of great importance because of its role in spatial prediction and design. In this paper, we propose a penalised likelihood approach with weighted L 1 regularisation to estimate the covariance matrix for spatial Gaussian Markov random field models with unspecified neighbourhood structures. A new algorithm for ordering spatial points is proposed such that the corresponding precision matrix can be estimated more effectively. Furthermore, we develop an efficient algorithm to minimise the penalised likelihood via a novel usage of the regularised solution path algorithm, which does not require the use of iterative algorithms. By exploiting the sparsity structure in the precision matrix, we show that the LASSO type of approach gives improved covariance estimators measured by several criteria. Asymptotic properties of our proposed estimator are derived. Both our simulated examples and an application to the rainfall data set show that the proposed method performs competitively.