测试数据来自 IkeLiu/1007

题目背景

家鸡是一个超级~~小黑子~~ikun。一天，他在网上发现他的偶像的演唱会将在n个城市举办。于是，他迅速叫来了他的好友fire_dragon和Ike_Liu帮他去那些城市买票。（那些演唱会的时间不必在意，只需要关注票卖完的时间）。

题目描述

现在，给出城市数量n(从1到n，家鸡用0表示)，并给出三人的移动速度为每小时a,b,c km（当然是开车），以及每场演唱会的举办城市和家鸡之间的路径数k（无向图）。第i场演唱会现在只剩了\(s~i~\)张票，而每小时都会卖出\(t~i~\)张票，家鸡希望能买到尽可能多的票。请输出他最多能买到多少票（在卖完时到达不算）

输入样例

第一行为两个整数，为n和k。
第2~k+1行，每行三个整数，分别是每条路径连接的两个城市代号和该路径的长度（km）。
第k+2~k+n+1行，每行两个整数，分别是\(s~i~\)和\(t~i~\)。
最后一行有三个实数，为a,b,c。

2 3
0 1 5
0 2 10
1 2 5
114514 114
1919810 191981
1 1.1 0.9

输出样例

一行，一个整数，为家鸡最多能买到多少票。

2

提示

1<=k,n<=1000,其余数皆在int范围内。