A saleswoman based in Vienna needs to plan her upcoming tour through Austria, visiting each province capital once. Help find the shortest route. Distances in km:
1=Vienna, 2=St. Pölten, 3=Eisenstadt, 4=Linz, 5=Graz, 6=Klagenfurt, 7=Salzburg, 8=Innsbruck, 9=Bregenz
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 1 | 0 | 65 | 60 | 184 | 195 | 319 | 299 | 478 | 631 |
| 2 | 65 | 0 | 125 | 119 | 130 | 254 | 234 | 413 | 566 |
| 3 | 60 | 125 | 0 | 184 | 157 | 281 | 261 | 440 | 593 |
| 4 | 184 | 119 | 184 | 0 | 208 | 252 | 136 | 315 | 468 |
| 5 | 195 | 130 | 157 | 208 | 0 | 136 | 280 | 459 | 629 |
| 6 | 319 | 254 | 281 | 252 | 136 | 0 | 217 | 391 | 566 |
| 7 | 299 | 234 | 261 | 136 | 280 | 217 | 0 | 188 | 343 |
| 8 | 478 | 413 | 440 | 315 | 459 | 391 | 188 | 0 | 157 |
| 9 | 631 | 566 | 593 | 468 | 629 | 566 | 343 | 157 | 0 |