Printing all paths of a tree and sorting the weight of edges
You can't do better than $\Omega(n^3)$ running time.

In a tree, there is a path between every pair of vertices, so there are $\Theta(n^2)$ paths.  The average path length can be $\Theta(n)$.  So the total length of the output can be $\Theta(n^3)$.  Obviously, no algorithm can run faster than that, since it takes at least $\Theta(n^3)$ time just to write out the output.