I'm trying to solve this problem too , my steps to solutions are ->
1. find all the shorthest ways with dijkstra
2. if there is only 1 or 2 ways printf solution
3.a take 2 longest ways , and let sum1=longestway1/2 sum2=longestway2/2
3.b try to split other ways in 2 gruops such that |(group1+sum1)-(group2+sum2)| is minimal
however this algo TLEs on step 3
I am doind subset sum DP for every possible sum till sumofallpaths/2 , because if i can make sumofall-i I can also get sum i
no need to check twice. Is there any faster way to do so?