For any who may find this in the future and are trying the same thing, I'll give some advice on what I had to do to get this solution to pass in Java:
1) Write your own heap for use in Dijkstra's. Java's priority queue is too slow.
2) Store data in parallel data arrays instead of having a pair object (this applies to both storing the adjacency list and the heap).
These were enough, on top of reading the input more efficiently than standard. I played around until I found out how big I had to make my heap, too. That helped so I didn't waste time growing it when necessary. The only run-time instantiation I ended up needing was to create the adjacency list, but doing this as an array instead of an ArrayList was probably the single biggest time saver of the program.