I was in a similar situation where I got a contract job via a staffing agency in a large consultancy firm and via the consultancy firm I worked for another company.
Although I had a legal contract with the staffing agency, I first notified the consultancy firm because I wanted to keep a good relationship with them and I explained my reasoning for leaving.
The staffing agency was not really happy with it but I knew I was not going to work with them anymore (I was actually tired of being sold "via via" like a product and them profiting from my work). I knew that I may have some possibilities with the consultancy firm in the future though.
A manager in the consultancy firm left me with a recommendation and even contacted me later to see if I wanted to return.
I am convinced that if I had not done things this way, I would not have been able to keep the good relationship I have with the manager from the consultancy firm.
If I were you, I would determine first who is important to you or could be important to you, and take your action accordingly. As other answers have stated, if you are unsure, just talk to the one you have a contract with.