Phinary representation

$\varphi =\frac{1+\sqrt{5}}{2}$ is the golden ratio.
Any positive integer can be represented as a sum of powers of $\varphi$ with integer exponents:

• $1={\varphi }^0$
• $2={\varphi }^1+{\varphi }^{-2}$
• $3={\varphi }^2+{\varphi }^{-2}$
• $4={\varphi }^2+{\varphi }^0+{\varphi }^{-2}$
• $5={\varphi }^3+{\varphi }^{-1}+{\varphi }^{-4}$
• $6={\varphi }^3+{\varphi }^1+{\varphi }^{-4}$
• $7={\varphi }^4+{\varphi }^{-4}$
• $8={\varphi }^4+{\varphi }^0+{\varphi }^{-4}$
• $9={\varphi }^4+{\varphi }^1+{\varphi }^{-2}+{\varphi }^{-4}$
• $10={\varphi }^4+{\varphi }^2+{\varphi }^{-2}+{\varphi }^{-4}$

If we add the constraint that no exponent are consecutive, this representation is unique.
This representation is called the phinary representation of an integer.

For an integer n, we define M(n) as the sum of all exponents in its phinary representation: $$M(641)=\sum {641}_{\text{base-}\varphi }=\sum \{13,9,7,5,2,0,-3,-11,-14\}=8$$ In the range $[1,10000000]$, find the minimun for M, the first integer which reaches the minimum, the maximum, and the first integer which reaches the maximum

Answer format: $M_{min},n_{min},M_{max},n_{max}$ // -17,77,8,46 for the range $[1,100]$

[My timing: 10 sec]

P.S:
Thanks to sinan for his suggestions which made this problem more interesting.