问题 B: 夏日不再重现防（防ak信不信由你）
时间限制: 1 Sec 内存限制: 512 MB提交: 11 解决: 6
[状态] [讨论版] [提交] [命题人:]
题目描述
夏日不会重现因为这是圣诞节
高夫套和他的 girlfriend 都住在和歌山市但是高夫套住在市中心，而他的 girlfriend 却住在了友之岛上。又是一年的圣诞节于是高夫套想和他的 girlfriend 来场美妙的约会。他们因为非常想念对方而想在圣诞节当天尽快的见到对方，所以需要大师你来帮他们选择约会地点来让他们尽快相见以解决他们相思之情。两个人可以同时到达，也可以一方先行到达去等待另一方，男女平等。
现在已知他们共有 n 个地点可以作为碰头地点（共 n 个地点分别用整数 1~n 进行标记，市中心的标号为 1，友之岛标号为 n ，怎么能住这么远的）
tips:可以在标号为 1 和 n 的位置碰头
现在你的手里有 m 份缺德地图，每一份上面详细描述了一些相互连通的地点，以及在这张图的交通体系下相互连通地点之间相互到达所需要的时间。
题目保证不会出现到达不了的情况，因为他俩要约会！
输入
输出
样例输入
Copy
5 4
1 3 1 2 3
2 2 3 4
10 2 1 5
3 3 3 4 5
样例输出 Copy
3
3 4
提示
对于题目中所给的样例
第一张地图上 任意两点相互到达的时间成本是 1，地图上共有 3 个点 1 2 3
第二张地图上 任意两点相互到达的时间成本是 2，地图上共有 2 个点 3 4
第三张地图上 任意两点相互到达的时间成本是 10 ，地图上共有 3 个点 2 1 5
第四张地图上 任意两点相互到达的时间成本是 3 ，地图上共有 3 个点 3 4 5
所以有两种方案，时间最少花费为 3
方案一：高夫套先花费 1 到达位置 3，等待另一方；另一方从位置 5 花费 3 到达位置 3，二者成功约会可喜可贺。
方案二：高夫套先花费 1 到达位置 3，然后花费 2 到达位置；另一方从位置 5 花费 3 到达位置 4，同时到达，二者成功约会可喜可贺。
第一张地图上 任意两点相互到达的时间成本是 1，地图上共有 3 个点 1 2 3
第二张地图上 任意两点相互到达的时间成本是 2，地图上共有 2 个点 3 4
第三张地图上 任意两点相互到达的时间成本是 10 ，地图上共有 3 个点 2 1 5
第四张地图上 任意两点相互到达的时间成本是 3 ，地图上共有 3 个点 3 4 5
所以有两种方案，时间最少花费为 3
方案一：高夫套先花费 1 到达位置 3，等待另一方；另一方从位置 5 花费 3 到达位置 3，二者成功约会可喜可贺。
方案二：高夫套先花费 1 到达位置 3，然后花费 2 到达位置；另一方从位置 5 花费 3 到达位置 4，同时到达，二者成功约会可喜可贺。