猫史档案馆

题目描述：乡村改造组委会准备首先在BZ镇实施改造。BZ镇共有n个村庄，有一些村庄之间连有土路，共m条。保证所有村庄之间都能通过土路连通。土路是双向的。村庄u，v之间的土路具有长度w(u,v)。现在组委会要将其中n-1条土路改造成公路，要求所有村庄之间都能通过公路连通。组委会想要使得所有公路的长度之和最小。

改造完毕后，长度为w的土路的通过时间为w，长度为w的公路的通过时间为w/2（向上取整）。询问从村庄a到村庄b最短通行时间。

输入格式：第一行两个正整数n，m；之后m行每行三个正整数u，v，w(n,v)，表示村庄u，v之间的土路具有长度w(u,v)；最后一行两个正整数a，b。

样例输入：

4 5
1 2 3
1 3 4
2 3 5
2 4 1
3 4 9
1 4

样例输出：

3

样例解释：改造(1,2)，(1,3)，(2,4)后，从1到4最短的时间为3（1->2->4）。

（个人感觉是最小生成树+最短路）