Distributed energy storage is a promising emerging technology for smart grid. In this paper, we address the question of optimally placing and sizing distributed storage resources in a network to minimize the cost of generation given a budget of available storage. For a non-decreasing convex generation cost, we prove that it is always optimal to place zero storage at generator buses that connect to rest of the grid via single links, regardless of demand profiles and network parameters. Hence, this defines a robust investment strategy for network planners. Besides, for a star network where the center is a generator bus and the other nodes are demand buses, we show that it is optimal not to place storage resources at the generator bus for small enough and large enough storage budget.