Before revision:  Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time  .
After revision:  Our analysis works on weighted graphs too, and is the first to achieve nearly-linear running time for these problems .