十二桥问题
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小多所在的城市可以看成是有n个点m条边的无向图（结点从1标号），每条边有一个距离d_i，其中有k条边是小希特别想走过的k座大桥。

小多和小希现在呆在1号结点，请你帮小多规划一条最短路线，使得小多和小希能从当前位置出发，并经过这k座桥，最后回到结点1。

点击下载大样例

输入描述:

第一行输入三个数n,m,k，分别表示结点数目，边数和小希特别想走过的大桥数目。

随后m行，第i行三个整数u_i,v_i,d_i，表示从u_i到v_i有一条距离为d_i的边。

其中前k条边即为小希想去的大桥。

输出描述:

输出一行，一个整数，表示满足条件的最短距离的路径长度。
示例1

输入

复制 
3 4 2
2 3 5
2 2 10
1 2 1
3 1 4

输出

复制 
20

说明

小希按线路1->2->2->3->1，分别花费1,10,5,4，共计20。

备注:

对于 100% 的数据，整张图联通，。