1856: 火焰巨魔的惆怅

【背景】巨魔家族在某天受到了其他种族的屠杀，作为一个英雄，他主动担任了断后的任务，但是，在巨魔家族整体转移过后，火焰巨魔却被困住了，他出逃的方式也只有召唤小火人这一种方式，所以请你帮助他。

【描述】我们把火焰巨魔所处的位置抽象成一张有向图，他的位置就是1号点位，目的就是走到第N号点位，因为小火人会裂嘛，所以我们可以看做每单位时间，小火人的数量会加倍，而每条路上的敌人有多强，会消耗多少小火人c[i]也会给出，如果小火人死光了，那么火焰巨魔也就可以看做是挂了，毕竟智力型英雄就是脆啊，当然有些时候也会遇到魔法泉之类的东西，这时候就可以补充一些小火人咯。希望你帮助火焰巨魔用最少的初始小火人逃离这次屠杀。

第一行两个数N（<=5000），M（<=100000）表示点位数与边数。

一下M行，每行三个数a，b，c表示a，b两点间的边权是c（|c|<=10000）

输出仅一个整数，表示最小初始小火人数。

5 4
1 2 -3
1 3 -6
3 4 1
4 5 -9

4