This paper presents a mathematically rigorous framework of remarkably-robust signal recovery over networks. The proposed framework is based on the minimax concave (MC) loss, which is a weakly convex function so that it attains (i) remarkable outlier-robustness and (ii) guarantee of convergence to a solution of the posed problem. We present a novel problem formulation which involves an auxiliary vector so that the formulation accommodates statistical properties of signal, noise, and outliers. We show the conditions to guarantee convexity of the local and global objectives. Via reformulation, the distributed triangularly preconditioned primal-dual algorithm is applied to the posed problem. The numerical examples show that our proposed formulation exhibits remarkable robustness under devastating outliers as well as outperforming the existing methods. Comparisons between the local and global convexity conditions are also presented.