Adjacency List

Use a sparse matrix.

Drawback: deleting an edge or looking up its weight is O(E), not constant time.