This work proposes an approach to speed up finite-time consensus algorithm using the weights of a weighted Laplacian matrix. It is motivated by the need to reach consensus among states of a multi-agent system in a distributed control/optimization setting. The approach is an iterative procedure that finds a low-order minimal polynomial that is consistent with the topology of the underlying graph. In general, the lowest-order minimal polynomial achievable for a network system is an open research problem. This work proposes a numerical approach that searches for the lowest order minimal polynomial via a rank minimization problem using a two-step approach: the first being an optimization problem involving the nuclear norm and the second a correction step. Convergence of the algorithm is shown and effectiveness of the approach is demonstrated via several examples. (C) 2018 Elsevier Ltd. All rights reserved.