This paper addresses the problem of initial synchronization of users in an indoor mm-Wave scenario. By using a massive number of antenna elements at access nodes, the resulting beams have narrow beamwidth. However, the transmission of individual narrow beams may cause poor coverage in some areas as the energy is concentrated over the direction of their main lobes. To cope with that, a beam sweep procedure using phased arrays is adopted. Access nodes simultaneously transmit individual beams until a certain area of interest is thoroughly scanned. The goal is to find the minimum power setting by adjusting the individual power levels so that users over the scanned area can observe a minimum received power level. The problem is formulated as a total consumed power minimization, suitably modeled for the standard min-sum algorithm. The proposed graph-based algorithm features some modifications in the message computation to decrease computational complexity, and adopts a random message-passing scheduling to deal with convergence issues. Simulation results indicate that the proposed algorithm usually outperforms a baseline iterative one, consuming about 13% less power in a typical simulation setup adopted.