现有个城市，以及条双向公里连接着某些城市。第条双向公路连接着，通过它的路费为。现在有一部电影在这个城市上映，第个城市的票价为。如果一个人在号城市，那么他想看到这个电影最少要花多少钱？（如果前往其他城市观看，则不必把回程的路费计入）。请将中每个数分别作为计算并求出答案。

输入描述:

第一行两个整数接下来一行个整数表示接下来行每行三个整数表示

输出描述:

一行个整数，第个整数表示时的答案。