问题1112--ZHAN与形政论文

1112: ZHAN与形政论文

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 64 MB

提交

题目描述

    今年是2020年,我们将全面建成小康社会,形势与政策课的主题自然也有相关内容。ZHAN决定以此为主题写一篇课程论文。

    众所周知,"要想富,先修路",ZHAN已经获得了某地的道路相关数据,但还需要一些处理才能写进论文里。

    该地有nn个聚居点,编号为11nn,其中11号聚居点为县城,其他聚居点是村庄。有一些道路将村庄与县城、村庄与村庄连接起来,两个聚居点之间可能有多条道路相连。现在,ZHAN想要知道,所有村庄到县城的路程之和最短是多少。

    测试数据保证所有村庄都可以到达县城。

输入

    第一行两个整数nnmm(2n1000,n1m100000)(2≤n≤1000,n−1≤m≤100000),表示有nn个聚居点,mm条道路。

    接下来mm行,每行三个整数u,v,wu,v,w(1u,vn,1w10000,uv)(1≤u,v≤n,1≤w≤10000,u≠v),表示聚居点uu和聚居点vv之间有一条路程为ww的道路。

输出

    一行,一个整数,表示所有村庄到县城的路程之和的最小值。

样例输入 Copy

3 4
1 2 3
2 3 4
1 3 2
2 1 4

样例输出 Copy

5

来源/分类