Minimum spanning tree - Prim's algorithm I have to demonstrate Prim's algorithm for an assignment and I'm surprised that I found two different solutions, with different MSTs as an outcome. Now I now that shouldn't happen, so I wonder what I did wrong ?

Here is the exercise: 


The first solution (using Prim's) is visiting the nodes in the following order: v0,v1,v8,v7,v6,v3,v2,v4,v5 Here the MST has a weight of 37, which is the same result that I got by using Kruskal's on the same graph.

The second solution (again using Prim's) however is the following order of visited notes: v0,v1,v3,v2,v7,v8,v6,v4,v5 , which leads to a MST with a weight of 39. How can this be ? Where is my mistake ? 

Thanks in advance
Prim's algorithm could give different solutions (depending on how you resolve "ties"), but all solutions should give a MST with the same (minimal) weight, which is not the case here.

Your second solution: $v_0,v_1,v_3,v_2,v_7,v_8,v_6,v_4,v_5$ is incorrect. After adding $v_0,v_1,v_3,v_2$ you add $v_7$. But the minimum distance between $v_7$ and any existing vertex in the tree is $6$. Vertex $v_6$ however has a distance of only $4$, and should thereby be added first. 

You could continue this, and end up with a solution that is indeed different from your solution 1, but has the same weight. For example, $v_0,v_1,v_3,v_2, v_6, v_7,v_8,v_4,v_5$, which gives an MST of weight $37$, as expected.