有6个城市，任何两个城市之间都有一条道路连接，6个城市两两之间的距离如下表，则城市1到城市6的最短距离为

城市1

城市2

城市3

城市4

城市5

城市6

城市1

0

2

3

1

12

15

城市2

2

0

2

5

3

12

城市3

3

2

0

3

6

5

城市4

1

5

3

0

7

9

城市5

12

3

6

7

0

2

城市6

15

12

5

9

2

0