C. 魔法禁林

开学的第一天，小 M 迫不及待地计划着前往神秘的禁林。

小 M 拥有两个重要的属性，魔力值和生命值。非常特别的是，初始时，这两个值可以由小 M 任意决定。

禁林可以看作一张 个点 条边的无向简单连通图。小 M 将在禁林里面行走，从起点 走到 。

每经过一条边，小 M 的魔力值都会减去 1。同时，每条边上有一个具有攻击力属性的魔兽，小 M 要与之战斗。若小 M 经过这条边之前的魔力值为 ，这条边上魔兽的攻击力为 ，那么经过这条边时发生的战斗将会消耗 的生命值。魔兽不会被打败，因此多次经过同一条边，每次都会发生战斗。

小 M 需要保证，当他的魔力值消耗完时，他的生命值为 0，且此时走到 点。

你需要求出小 M 初始时需要的最小生命值。

输入格式

第一行四个整数 。

接下来 行，每行三个整数 ，表示编号为 的点之间有一条边，边上魔兽的攻击力为 。

输出格式

一行一个整数，表示小 M 初始时需要的最小生命值。

样例 #1

样例输入 #1

3 3 1 3
1 2 2
1 3 5
3 2 3

样例输出 #1

4

样例 #2

样例输入 #2

5 10 1 5
2 1 3
3 1 7
4 2 4
5 3 9
5 1 7
2 3 2
5 4 6
1 4 10
5 2 5
3 4 10

样例输出 #2

6

对于所有数据，，，，，图为无向简单连通图，。

【样例 1 解释】

初始时，小 M 选择魔力值为 ，生命值为 。

• ：魔力值剩余 ，生命值剩余 。
• ：魔力值剩余 ，生命值剩余 。

可以证明 为小 M 初始时需要的最小生命值。