  We study the directed last-passage percolation model on the planar square
lattice with nearest-neighbor steps and general i.i.d. weights on the vertices,
outside of the class of exactly solvable models. Stationary cocycles are
constructed for this percolation model from queueing fixed points. These
cocycles serve as boundary conditions for stationary last-passage percolation,
solve variational formulas that characterize limit shapes, and yield existence
of Busemann functions in directions where the shape has some regularity. In a
sequel to this paper the cocycles will be used to prove results about
semi-infinite geodesics and the competition interface.
