ยง Djikstra's using a segtree

keep min segtree of distances. Now just have to run n-1 interations. You like segtrees right :P