//codeforces 96D Volleyball
//http://codeforces.com/problemset/problem/96/D
/*
 * 题意：
 * Petya 搭taxi赶着去看volleyball match
 * 有n个街口，m条路
 * 街口由1--n标识
 * x，y标志开始街口和目的街口
 * 接下来m行，
 * 每行有ui,vi,wi，分别表示ui到vi有wi长
 * 接下来n行
 * ti，ci，表示每一个街道等待的taxi  的最长驾驶距离和收费
 * 如果不能到达y，则输出-1，否则输出最小费用
 * 解法：
 * 首先扩展每个点使用其本身的taxi能到达的点
 * 然后从起点开始bfs，每次选择一个代价最小的点继续扩展，直至发现目的点
 * 由于1000*1000的数据规模会导致mle，所以每次bfs时才扩展对应的点
 * author:licatweijie
 */