若求权值第k短路的同时要求字典序最小该怎么处理？

[SCOI2007]k短路

想了很久没有想到好写的方法...

想到了一种暴力的方法： 在最后求答案的小根堆的比较中，若权相等，暴力 $O(n)$ 判断字典序。

还有个问题是在每个节点维护的小根堆中，可能父节点与子节点权值相等，这时又如何处理？