题目描述

蛟龙六班的期末考试只有4道题，然而想要用这四道题考察六班学的所有知识点，当然这是不可能的，因此攀哥只能把两个知识点放在一个题目里考！ 最小最短路生成树，即最小的满足最短路性质的生成树，具体地来说，给定一个有n个点，m条无向边的图，请在这张图上选定若干条边形成生成树，要求生成树中：对于所有节点i，i到1号点的最短路Dis_tree[i]=原图中i到到1号点的最短路Dis_graph[i]。请输出所有满足条件的生成树中的最小的边权和。

输入格式

输入第一行为两个正整数n,m，表示图的点数和边数。 接下来m行，每行三个数，x[i],y[i],d[i]，表示一条x[i]连向y[i]的双向边，边权为d[i]。

输出格式

输出一行一个数，表示最短路生成树的权值。

输入样例1

5 10 1 2 4 1 5 4 1 3 5 2 3 3 2 4 2 2 5 1 3 5 3 3 4 1 4 5 1 5 5 5

输出样例1

14 说明：选择(1,2), (1,3), (1,5), (4,5),这四条边，总权值为14

输入样例2

5 6 1 2 1 1 3 2 1 4 3 2 5 7 3 5 6 4 5 5

输出样例2

11 说明：如果输出13可能是满足最短路但不满足权值和最小

数据说明

对于40%的数据，n≤6，m≤10； 对于60%的数据，n≤100，m≤1000； 对于100%的数据，n≤1000，m≤100000，1≤d[i]≤10000。